[boj] 미로 탐색_2178

처음 이 문제를 봤을 때에는 dfs를 이용해 해결하려고 했으나, 최솟값을 구해주기 위해선 백트래킹 알고리즘을 생각해줘야 했는데 이 부분이 어려워 bfs를 이용해 해결했다.

 

bfs는 큐를 이용해 문제를 해결하는데, 기초적인 이론으로 bfs를 설명하면 보통 그래프를 이용해 설명한다.(bfs알고리즘 포스팅 링크 첨부 예정)

 

이 문제는 x, y좌표를 이용한 이중 배열(리스트)를 이용하여 해결하는 문제였기 때문에 bfs 알고리즘을 실제로 코드에 녹여내기가 조금 어려웠다.

 

이런 문제처럼 x, y좌표를 통해 이중 배열(리스트)로 나타내는 모양을 이용하는 문제 유형이 대표적이니 반드시 익숙해져야 겠다고 느꼈다.

 

백준 예제 2번을 이용해 설명하겠다.

처음에 주어진 그래프가 있고 빈 큐를 선언했다.

 

처음 시작 부분의 좌표를 큐에 넣는다.

 

큐에서 첫 번째 요소를 꺼낸 뒤 (popleft 메소드) 해당 좌표 기준 네 방향을 탐색해 그래프가 의 값이 1이면 (전진 가능한 좌표면) 그 좌표를 큐에 넣어준다.

필자는 상, 하, 좌, 우 순서로 좌표를 넣어주었다.

그 후 해당 좌표에 있는 1을 이전 '이전 좌표에 있는 수 +1' 로 치환한다.

 

이제 큐의 다음 차례인 (1, 0) 좌표를 꺼내고 네 방향을 탐색한다.

(2, 0) 좌표와 (1, 1) 좌표가 전진할 수 있으므로 2에 1을 더한 3으로 매핑한다.

 

마찬가지로 (0, 1) 좌표도 큐에서 꺼내고 네 방향을 탐색한다. (0, 1) 좌표에서는 네 방향 중 처음 시작지를 제외하고는 전진할 수 없다.

(시작지가 1이 아니라 3으로 매핑되는 것은 이 알고리즘의 허점인데, 값을 출력하는 것에는 전혀 문제가 없다.)

 

(그림이 점점 알아보기 힘들게 지저분해진다...)

위와 동일한 방법으로 큐의 첫번째 좌표인 (2, 0)을 꺼내준 다음 네 방향 탐색을 실시하여 1인 좌표(전진할 수 있는 좌표)를 큐에 넣어준다.

이후에 값에 3+1인 4를 매핑해준다.

 

큐의 다음 좌표인 (1, 1)에서 동일하게 네 방향 탐색을 실시하면 네 방향에 1인 좌표가 없으므로 큐에는 아무런 좌표가 새로 추가되지 않는다.

 

위 방법을 큐가 비어있을 때 까지 반복해주면,

 

위와 같은 상태로 마무리된다.

 

위에서 언급한 대로 (0, 0) 좌표의 값이 1이 아니라 3으로 매핑되는 허점이 있으나, 최종 목적은 끝 좌표(N-1, M-1)의 값을 구하는 것이므로 값을 도출하는 데에는 영향을 주지 않는다.

 

# boj_2178 미로 탐색 https://www.acmicpc.net/problem/2178

from collections import deque

N, M = map(int, input().split())

graph = []
queue = deque()

for i in range(N):
    graph.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(start_x, start_y):
    queue.append([start_x, start_y])
    while queue:
        temp = queue.popleft()
        old_x = temp[0]
        old_y = temp[1]
        for i in range(4):
            new_x = old_x + dx[i]
            new_y = old_y + dy[i]

            if new_x >= N or new_x < 0 or new_y >= M or new_y < 0:
                continue

            if graph[new_x][new_y] == 1:
                queue.append([new_x, new_y])
                graph[new_x][new_y] = graph[old_x][old_y] + 1

bfs(0, 0)
print(graph[N-1][M-1])