[Python] 게임 맵 최단거리 - BFS

문제

해당 문제 링크

정답

from collections import deque
def solution(maps):
    answer = 0

    # 상하좌우
    # 상(-1, 0) 하(1, 0) 좌(0, -1) 우(0, 1)
    dx = [-1, 1, 0, 0] #행 이동
    dy = [0, 0, -1, 1] #열 이동

    def bfs(x, y):
        queue = deque()
        queue.append((x, y))

        # queue가 빌 때까지 반복
        while queue:
            x, y = queue.popleft()

            # 상하좌우 칸 확인하기
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                # 맵을 벗어나면 무시하기
                if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]): continue
                # 벽이면 무시하기
                if maps[nx][ny] == 0:  continue

                # 처음 지나가는 길이면 거리계산하고 다시 상하좌우 확인하기
                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))    # 재귀

        # 상대 팀 진영(제일 오른쪽 아래 칸)까지의 거리 반환
        return maps[len(maps)-1][len(maps[0])-1]

    answer = bfs(0, 0)
    return -1 if answer == 1 else answer    # 상대 팀 진영에 도착할 수 없을 때 -1

풀이

BFS/DFS 개념 공부는 했지만 문제를 어떻게 접근해야할지 몰랐다..
처음에는 이중 for문을 통해 0이라면 다음 행으로 이동하고, 1이라면 다음 열로 이동하게끔 하고자 했지만, 그렇게 되면 위로 올라가지는 못했다. 그래서 다른 사람들의 코드와 설명을 보고 가장 이해가 쉬운 코드로 공부해보자 했다.
각 코드에 대한 설명은 주석으로 보면 이해가 쉽다.