[프로그래머스 1844 파이썬] 게임 맵 최단거리 (level 2, BFS/DFS)

알고리즘 유형 : BFS/DFS
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/1844

소스 코드(파이썬)

from collections import deque

def move(x, y):
    yield (x-1, y)
    yield (x+1, y)
    yield (x, y-1)
    yield (x, y+1)

def solution(maps):
    answer = -1
    row = len(maps)
    col = len(maps[0])
    visited = [[False]*col for _ in range(row)]
    visited[0][0] = 1
    q = deque([(0, 0)])
    
    while q:
        x, y = q.popleft()
        
        if x == row-1 and y == col-1:
            answer = visited[x][y]
            break
        
        for adj_x, adj_y in move(x, y):
            if 0 <= adj_x < row and 0 <= adj_y < col:
                if visited[adj_x][adj_y] == False and maps[adj_x][adj_y] == 1:
                    q.append((adj_x, adj_y))
                    visited[adj_x][adj_y] = visited[x][y] + 1
    
    return answer

풀이 요약

1. 그래프에서의 간선, 즉 방문할 인접 노드를 직접 정의하고, 이동 횟수를 visited에 누적해가는 BFS 풀이로 풀면 된다.

2. 처음에 answer에 -1을 넣어둔다. BFS를 모두 끝마친 후에도 목적지에 도달하지 못해 answer를 갱신하지 못했다면 그대로 -1을 출력해주면 되는 것이다.

3. 큐에는 노드의 좌표를 넣어준다.

   이 후 큐가 빌 때까지 큐에서 원소를 꺼내 목적지인지 검사하고, 목적지라면 그 때의 visited를 기록, 아니라면 인접 노드로 탐색을 이어나간다.

   이 때 인접 노드로는 지도의 범위를 벗어나지 않는 한에서 동서남북 방향으로 진행한다.(제너레이터 활용)

   인접 노드의 조건은, 지도의 범위를 벗어나지 않고 visited가 False(미방문)이며 벽이 아니여야(maps 값이 0이 아니여야 함)한다.

   이를 만족하면 좌표를 큐에 넣고 visited를 이 전의 노드의 visited 값 + 1로 갱신해주면 된다.

배운 점, 어려웠던 점

• 최단 거리에 사용되는 BFS의 활용의 숙련도를 높일 수 있었다.