python으로 푸는 백준 15671. 오델로

백준 15671. 오델로

 문제는 SW Expert Academy 4615. 재미있는 오셀로 게임과 매우 유사한 문제이다. 

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

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

백준 덕분에 테스트 케이스도 한개가 더 느니까 테스트도 좀더 수월하다.

이 문제는 오셀로 규칙을 적용해서 흑,백의 돌을 두었을 때 맨 마지막 돌들이 어떻게 놓여져있는지와 승패를 출력하는 문제이다.

SW Expert Academy 4615. 재미있는 오셀로 게임 문제 풀이 보기

백준에서 문제 보기

백준에서 푼 문제 리스트 보기

github에서 코드 보기

문제에서 제시한 조건

문제를 푸는데 에러가 난다면 아래의 조건을 다시 읽어보자. 분명 빠뜨린 조건이 있다.

• 처음에 판 가운데 사각형으로 엇갈리게 배치된 돌 4개를 놓고 시작한다.
• 돌은 반드시 상대방 돌을 양쪽에 포위하여 뒤집을 수 있는 곳에 놓아야 한다. 
• 포위한다는 것은 두 돌 사이에는 반드시 상대의 돌만 있어야 한다는 의미이다. 빈칸이 있어서는 안된다.
• 돌을 뒤집을 곳이 없는 경우에는 차례가 자동적으로 상대방에게 넘어가게 된다. (input된 돌들만 다 처리해주면 된다)
• 돌을 어디에 둘지는 입력받을 거니, 조건에 맞게 돌만 잘 뒤집어 주고 갯수만 잘 세면 된다.

문제 풀때 고려할 사항

빈칸이 있다면 상대의 돌을 바꿀수 없다.

오셀로에서는 돌을 놓는것 말고도 사이에 내 색깔의 돌 사이에 낀 돌도 변경할 수 있는 규칙도 있는데, 이 문제를 풀때는 그건 신경 쓰지 말아야 한다.

문제 풀이

문제 자체는 어렵지 않다. 근데 오셀로 게임을 모르고 문제를 제대로 이해하지 않으면 조건들을 빼먹을 수 있다는게 문제이다.

내가 빼먹은 조건은, 두 돌은 상대의 돌을 감쌀 때, 빈 공간 없이 양 끝을 직접 막아야 한다는 조건이다. 

대각선에 바둑돌을 두었을 때, 그 사이에 상대의 돌이 얼마나 있고, 빈 공간의 유무와 돌을 뒤집어도 되는지 등등을 고려하는 것이 어려웠다.

사이에 둔다는 것은 가로, 세로, 대각선으로 상대의 돌을 끼고 돌을 둘 수 있다는 이야기이다.

나는 내가 놓을 돌(r,c)와 기존에 놓여있던 돌들의 위치 값을 비교하여 r이 같으면 같은 행에 위치, c가 같으면 같은 열에 위치에 있다고 처리했다.

기존 돌들의 위치 값을 pos이고 pos_r,pos_c로 구성되어 있다고 한다면 (r- pos_r)과 (c-pos_c)의 차의 절대값이 서로 같다면 대각선에 위치하는 바둑돌이라고 판단하고, pos의 돌의 위치에서 내가 놓을 돌(r,c) 쪽으로 한칸 씩 이동하면서 상대의 바둑돌인지 아닌지 체크하는 방식으로 코드를 구현하였다. 빈칸이 나올 경우에는 두 바둑돌 사이에서 여태까지 뒤집으려고 했던 바둑돌의 값을 초기화해주었다.

이 문제를 푸는데 평소에 잘 나지도 않던 런타임 에러도 났었고(함수와 전역변수의 변수명을 동일하게 작성해서 생긴 오류) 너무 당황했었다.

여태까지 백준에서 풀면서 런타임 에러가 난 적이 별로 없었는데 에러가 난 이유를 알려주지 않으니까 코드를 얼마나 들여다보았는지 모른다.

그때 내 알고리즘이 잘못되었는지 다른 사람의 코드를 많이 찾아보았었다.

다른 사람들은 위, 아래, 왼쪽, 오른쪽으로 순회할때마다 선언했던 리스트를 오셀로 규칙에 따라 모두 만들어서 반복문을 활용해 바둑돌을 뒤집어 나가는 것을 보았다.

나중에이런 유형의 문제를 풀기 위해 코드를 짠다면 그 방식이 문제 푸는 시간도 덜들고 좋아보여서 차용해 볼 생각이다. 

내 방식대로 풀면 이 문제를 오래 들여다보다보니 pos가 (r,c)와 간격을 좁혀 나갈때, 값을 1만큼 더해야 하는지, 빼야하는지 헷갈리기 시작했다.

내 방식도 나쁘지는 않았지만, 나중에 유사한 문제를 풀게 되었을 때를 대비해서 패턴을 만들 수 있을 것 같다. 

파이썬 코드

 
import sys
input = sys.stdin.readline
 
def changeArr(arr, color_list, pos, color):
    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
                # 범위 초과시 처리
                # count에서 이미 처리했으므로 필요 없는 코드이나 예방 차원으로 넣음
                if pc < 0 or pc > 5:
                    temp = set()
                    break
                # 내 색의 돌이 나올 경우 뒤집기 취소
                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 pr < 0 or pr > 5:
                    temp = set()
                    break
                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 pr < 0 or pc < 0 or pr > 5 or pc > 5:
                            temp = set()
                            break
                        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 pr < 0 or pc < 0 or pr > 5 or pc > 5:
                            temp = set()
                            break
                        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 pr < 0 or pc < 0 or pr > 5 or pc > 5:
                            temp = set()
                            break
                        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 pr < 0 or pc < 0 or pr > 5 or pc > 5:
                            temp = set()
                            break
                        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):
    # setting
    black_list = set()
    white_list = set()
 
    r = (6//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] = 'W', 'W'
    arrList[r+1][r], arrList[r][r+1] = 'B', 'B'
 
    # 기존에 놓여 있던 돌과 새로운 돌의 위치를 비교하며 하나씩 체크
    for position in posList:
        color = position[1]
        pos = position[0]
        color_list = white_list
 
        if color == "B":
            color_list = black_list
 
        # 뒤집어야 하는 상대방의 돌 위치
        changed = changeArr(arr, color_list, pos, color)
 
        for p in changed:
            arr[p[0]][p[1]] = color
 
        # 뒤집은 돌의 정보를 list에 기록
        if color == "B":
            black_list.update(changed)
            white_list.difference_update(changed)
 
        else:
            white_list.update(changed)
            black_list.difference_update(changed)
 
    # 격자판 출력
    for li in arr:
        print("".join(li))
 
    # 승패 출력
    if len(black_list) > len(white_list):
        print("Black")
    else:
        print("White")
 
 
if __name__ == "__main__":
    n = int(input().strip())  # log count
    arrList = [["."]*6 for i in range(6)]
 
    # 흙돌이 선을 잡는다.
    posList = []
    for i in range(n):
        color = "W" # 백
        if (i % 2) == 0:
            color = "B" # 흑
        r,c = map(int, input().strip().split())
        pos = ((r - 1, c - 1), color)
        posList.append(pos)
 
    solve(posList, arrList)
 

#백준 15671. 오델로 #백준 오델로 #백준 오델로 python #python 백준 오델로 #백준 15671 오델로 #15671 오델로 백준 #백준 15671 #재미있는 오셀로 게임 #삼성 재미있는 오셀로 게임 #파이썬 오델로 #파이썬 오셀로 #백준 오셀로 #오셀로 백준 파이썬 #파이썬 오셀로 문제 #오셀로 파이썬 #sw expert 오셀로