Python으로 푸는 SW Expert Academy 4615. 재미있는 오셀로 게임

SW Expert Academy [2차원 배열 탐색 연습문제] 4615. 재미있는 오셀로 게임

문제에서는 오셀로라는 게임의 규칙에 따라 흑,백의 돌을 놓고

플레이어가 돌을 모두 두었을 때, 게임판에 올려진 흑,백의 돌의 개수를 각각 출력해야 한다.

이 문제는 백준 15671. 오델로와 유사한 문제기 때문에, 이 문제를 푼다면 백준의 문제도 풀 수가 있다.

만약 SW Expert Academy 4615. 재미있는 오셀로 게임을 푸는데 테스트 케이스를 모두 통과하지 못한다면

게임판을 6*6 크기로 한정한 백준의 오델로 문제를 먼저 풀어보자.

삼성 SW Expert Academy에서 푼 문제 리스트 보기

백준 15671. 오델로 풀이 보러 가기

github에서 코드 보기

문제에서 제시한 조건

자신이 놓을 돌과 자신의 돌 사이에 상대편의 돌이 있을 경우에만 그 곳에 돌을 놓을 수 있다.

테스트 케이스를 통과하지 못했다면 확인할 사항

돌과 돌 사이에 상대방의 돌이 있다는 것은 그 사이에 빈칸이 존재해서는 안된다는 의미이다. 

(0,0)에 흑돌(2)을 놓는 경우에 빨간색 1(1,0)과 파란색 1(1,1) 중에서 파란색 1(1,1)만 값이 변경된다. (2,0)에 빈칸이 있기 때문에 변경 될 수 없다.

<초기 모습> 1의 갯수 : 6 , 2의 갯수 : 2

arr = [  

    [(2),  1,  1, 0],

    [  1,  1,  1, 0],

    [ 0, 1, 2, 0],

    [ 2, 0, 0, 0],

]

<변경된 모습> 1의 갯수 : 5 , 2의 갯수 : 4

arr = [  

    [ 2,  1,  1, 0],

    [ 1,  2,  1, 0],

    [0,  1,  2, 0],

    [ 2, 0, 0, 0],

]

풀이

나는 기존에 놓여 있던 돌들의 위치와 새로운 돌의 위치를 비교해서 같은 행에 위치, 같은 열에 위치, 대각선상에 위치 하는지를 먼저 파악했다.

기존 돌 (pos_r, pos_c), 새로운 돌(r, c)이라고 한다면,

기존 돌과 새로운 돌이 같은 행에 위치 : pos_r과 r이 같다.

기존 돌과 새로운 돌이 같은 열에 위치 : pos_c와 c가 같다.

기존 돌과 새로운 돌이 대각선상에 위치 : 절대값 (pos_r - r) == 절대값 (pos_c - c)이 일치

기존 돌과 새로운 돌이 같은 행, 같은 열, 대각선상에 위치할 경우에 상대의 돌을 뒤집어 주었다.

다만, 문제를 풀다보면 위에 정리해둔 '테스트 케이스를 통과하지 못했다면 확인할 사항'에서의 상황은 어떻게 처리해야 하는지 의문이 들 수 있다. 

두 돌이 상대의 돌을 감쌀 때, 상대의 돌을 뒤집으려면 반드시 빈 공간 없이 양 끝을 직접 막아야 한다. 이 조건을 기억하고 문제를 풀면 쉽게 풀 수 있다.

파이썬 코드

"""
SW Expert Academy 4615. 재미있는 오셀로 게임
blog : https://daimhada.tistory.com/59
"""
 
def changeArr(arr, color_list, pos, color, n):
    r, c = pos
    changed = set()
    changed.add((r, c))
    for po in color_list:
        pr, pc = po[0], po[1]
        temp = set() # 변경 예정인 돌들을 넣는다.
        # 가로, 세로, 대각선인지 체크
        # 기존 돌(po)이 새로 놓을 돌의 위치로 이동하듯 상대돌이 있는지 체크
        if pr == r:
            count = abs(pc - c) - 1
            # 같은 가로줄에 위치, pc가 c가 되도록 수를 1만큼 더하거나 빼준다
            while count:
                count -= 1
                if pc > c:
                    pc -= 1
                else:
                    pc += 1
                # 내 색의 돌이 나올 경우 뒤집기 취소
                if arr[r][pc] == color:
                    temp = set()
                    break
                # 빈 칸이 나올 경우 뒤집기 취소
                if arr[r][pc] == '.':
                    temp = set()
                    break
                # 변경할 임시 돌들을 저장함
                temp.add((r, pc))
            changed.update(temp) # 변경할 돌 리스트에 추가
        elif pc == c:
            count = abs(pr - r) - 1
            # 같은 세로줄에 위치, pr이 r이 되도록 수를 1만큼 더하거나 빼준다.
            while count:
                count -= 1
                if pr > r:
                    pr -= 1
                else:
                    pr += 1
 
                if arr[pr][c] == color:
                    temp = set()
                    break
 
                if arr[pr][c] == '.':
                    temp = set()
                    break
                temp.add((pr,c))
            changed.update(temp)
        elif abs(pr - r) == abs(pc - c) and abs(pc - c) > 1:
            # 돌이 대각선상에 위치
            # 기존 돌(po)이 새로운 돌이 있는 곳까지 대각선으로 한칸씩 이동한다.
            count = abs(pr - r) - 1 # 최대 count만큼 반복하면 된다.
 
            if pr > r:
                # 기존 돌(po)이 새로운 돌(r,c)보다 아래에 위치 (pr 감소)
                if pc > c:
                    # 기존 돌(po)가 새로운 돌(r,c)보다 오른쪽에 위치 (pc 감소)
                    while count:
                        pr -= 1
                        pc -= 1
                        count -= 1
                        if arr[pr][pc] == color:
                            temp = set()
                            break
                        if arr[pr][pc] == '.':
                            temp = set()
                            break
                        temp.add((pr, pc))
                    changed.update(temp)
                else:
                    # 기존 돌(po)가 새로운 돌(r,c)보다 왼쪽에 위치 (pc 증가)
                    while count:
                        pr -= 1
                        pc += 1
                        count -= 1
                        if arr[pr][pc] == color:
                            temp = set()
                            break
                        if arr[pr][pc] == '.':
                            temp = set()
                            break
                        temp.add((pr, pc))
                    changed.update(temp)
            else:
                # 기존 돌(po)이 새로운 돌(r,c)보다 위에 위치 (pr 증가)
                if pc > c:
                    # 기존 돌(po)이 새로운 돌보다 오른쪽에 위치 (pc 감소)
                    while count:
                        pr += 1
                        pc -= 1
                        count -= 1
                        if arr[pr][pc] == color:
                            temp = set()
                            break
                        if arr[pr][pc] == '.':
                            temp = set()
                            break
                        temp.add((pr, pc))
                    changed.update(temp)
                else:
                    # 기존 돌(po)이 새로운 돌보다 왼쪽에 위치 (pc 증가)
                    while count:
                        pr += 1
                        pc += 1
                        count -= 1
                        if arr[pr][pc] == color:
                            temp = set()
                            break
                        if arr[pr][pc] == '.':
                            temp = set()
                            break
                        temp.add((pr,pc))
                    changed.update(temp)
    return changed
 
def solve(posList, arr, n):
    black_list = set()
    white_list = set()
    # setting
    r = (n//2) - 1
    white_list.update([(r,r),(r+1, r+1)])
    black_list.update([(r+1,r),(r, r+1)])
    arrList[r][r], arrList[r+1][r+1] = 2, 2
    arrList[r+1][r], arrList[r][r+1] = 1, 1
 
    for position in posList:
        color = position[1]
        pos = position[0]
        color_list = white_list
 
        if color == 1:
            color_list = black_list
 
        changed = changeArr(arr, color_list, pos, color, n)
        for p in changed:
            arr[p[0]][p[1]] = color
 
        if color == 1: # black
            black_list.update(changed)
            white_list.difference_update(changed)
 
        else:
        # white
            white_list.update(changed)
            black_list.difference_update(changed)
 
    return len(black_list), len(white_list)
 
 
if __name__ == "__main__":
    t = int(input().strip())  # test case count
    for i in range(t):
        n, m = map(int, input().strip().split())
        arrList = [["."]*n for i in range(n)]
 
        # 흙돌이 선을 잡는다.
        posList = []
        for i2 in range(m):
            c, r, color = map(int, input().strip().split())
            pos = ((r - 1, c - 1), color)
            posList.append(pos)
 
        black, white = solve(posList, arrList, n)
        print('#{0} {1} {2}'.format(i+1, black, white))
 

#sw expert 4615 #sw expert 4615 재미있는 오셀로 게임 #sw expert 4615. 재미있는 오셀로 게임 #삼성 재미있는 오셀로 게임 #SW Expert 재미있는 오셀로 게임 #재미있는 오셀로 게임 삼성 #재미있는 오셀로 게임 python #python 오셀로 게임 #줄기세포 배양 3차시#줄기세포 배양 문제들 #2차원 배열 탐색 오셀로 #파이썬 4615 재미있는 오셀로 게임 #4615. 재미있는 오셀로 게임 파이썬 #삼성 4615. 재미있는 오셀로 게임