오델로 문제 - programmers

1 DFS로는 풀리지 않는다.

오랫만에 풀어본 DFS. 시험 볼 때는 시간 부족으로 못 풀었기 때문에 복기한다. dfs는 dfs를 어디서 진입해야하는지 정하는게 처음에 중요하다. 그리고 대부분은 어떤 조건을 count 한다던지 하는데(오델로의 경우에는 뒤집힐 검은 돌의 숫자) 그런 로직을 따로 함수로 분리해서 생각하는게 편하다. 여기에서는 findblack 함수가 그 역할을 한다)

하지만 아래 코드는 시작점이 Black인 경우에 실패하고 있으므로 추가 수정이 필요하다.

def solution(board):
    arr = [[0]*len(board) for _ in range(len(board))]
    v = [[False]*len(board) for _ in range(len(board))]
    # 8방향
    dy = [0,-1, 0 , 1, 1,-1,1,-1]
    dx = [1, 0, -1, 0,-1,1,1,-1]
    start = (0,0)

    def findblack(i:int, x, y):
        """
        정해진 방향으로 진행했을 때 흑돌을 잡을 수 있다면 흑돌의 개수를 반환하는 함수이다
        """
        count = 1
        ny = y + dy[i]
        nx = x + dx[i]
        while board[ny][nx] == 'B':
            ny += dy[i]
            nx += dx[i]
            count +=1
        if board[ny][nx] == 'W':
            print(f"black mark {count}")
            return count
        else:
            return 0

    # 탐색문
    def dfs(x,y):
        v[y][x] = True
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if board[y][x] == 'W' or board[y][x] == 'B':
                dfs(nx,ny)
            if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board) or board[ny][nx] == 'W':
                continue
            if v[ny][nx]:
                continue
            else:
                #v[ny][nx] = True
                print(f"checking out : ({nx},{ny})")
                if board[ny][nx] == 'B': # valid
                    print(f"direction is {i}")
                    arr[y][x] += findblack(i, nx, ny)
                    #dfs(nx,ny)
                else:
                    print(f"moving to ... {nx}, {ny}")
                    dfs(nx,ny)

    dfs(start[0],start[1])
    for i in range(len(arr)):
        print(arr[i])



if __name__ == "__main__":
    tc1 = ["......",".B.W..",".B.BBW",".BBBBW","..WBW.",".W...."]
    solution(tc1)
    # tc2 = ["...",".B.","WW."]
    # solution(tc2)

2 완탐이 맞는 풀이다.

문제를 다시 간단한 완탐으로 풀어보았다. 정답에 가까워진것 같다.

def solution(board):
    arr = [[0]*len(board) for _ in range(len(board))]
    v = [[0]*len(board) for _ in range(len(board))]
    # 8방향
    dy = [0,-1, 0 , 1, 1,-1,1,-1]
    dx = [1, 0, -1, 0,-1,1,1,-1]
    # dy = [0,-1, 0 , 1]
    # dx = [1, 0, -1, 0]
    start = (0,0)

    def findblack(i:int, x, y):
        """
        정해진 방향으로 진행했을 때 흑돌을 잡을 수 있다면 흑돌의 개수를 반환하는 함수이다
        """
        count = 1
        ny = y + dy[i]
        nx = x + dx[i]
        if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board):
            return 0
        while board[ny][nx] == 'B':
            ny += dy[i]
            nx += dx[i]
            count +=1
            if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board):
                return 0
        if board[ny][nx] == 'W':
            #print(f"black mark {count}")
            return count
        else:
            return 0

    for j in range(len(board)):
        for i in range(len(board)):
            if board[j][i] == 'W' or board[j][i] == 'B':
                continue
            if board[j][i] == '.':
                for m in range(8):
                    nx = i + dx[m]
                    ny = j + dy[m]
                    if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board):
                        continue
                    elif board[ny][nx] == 'B' and board[j][i] == '.': # valid
                        arr[j][i] += findblack(m, nx, ny)
    for a in arr:
        print(a)



if __name__ == "__main__":
    # tc1 = ["......",".B.W..",".B.BBW",".BBBBW","..WBW.",".W...."] #6X6
    # solution(tc1)
    tc2 = ["B.W..","B.BBW","BBBBW",".WBW.","W...."] # 5X5 시작점이 검은 돌인 경우를 test 해보자
    solution(tc2)
    # tc2 = ["...",".B.","WW."]
    # solution(tc2)