백준 2178 : 미로 탐색 (파이썬)

BFS 를 이용한 탐색 문제이다.

 

미로의 탈출 가능한 최단 경로를 찾는 문제인데,

사방 탐색은 여러 가지 구현 문제를 풀었던 경험으로 쉽게 떠올릴 수 있었지만 탐색 후 올바른 경로에 대해 BFS를 적용하려고 하니 난해했다.

 

코드를 완성시킨 후 다시 리뷰하면서 파악해보니 눈에 좀 익으면서 어느 정도 파악이 되었는데,

1. 정해진 범위 내에서 탐색을 진행하며
2. 현재 보고있는 정점과 인접한 정점 중 이어진 곳 따라 탐색을 진행하면서
3. 자신이 왔던 길이 아닌 앞으로 가야할 길의 좌표, 즉 자기가 왔던 곳을 제외한 인접정점들을 for 문을 통해 순서대로 queue 에 넣고
4. 그 인접정점의 값에는 기존의 1 이라는 값 대신 (인접 정점의 기존 값 + 자기 자신의 값) 을 새로 넣어준다.
5. queue 의 왼쪽에서 하나씩 꺼내며 탐색을 진행한다. 

위의 전개를 그대로 코드로 옮기면 되는 문제였다.

 

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
maze = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if not maze[nx][ny]:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] += maze[x][y]
                queue.append((nx, ny))
for _ in range(N):
    maze.append([*map(int, sys.stdin.readline().strip())])
bfs(0, 0)
print(maze[-1][-1])

 

이 때 위의 BFS 코드 흐름 중 세 번째 조건문의 경우, 계산된 좌표가 탐색해야 할 좌표인지 아닌지를 구분하는 것으로,

 

if maze[nx][ny] == 1:

 

위와 같이 했어야 했는데 내 경우는,

 

if maze[nx][ny]:

 

위 처럼 써서 틀렸다.

 

단순히 0 이 아닌 경우는 무조건 길이니까 그렇게 탐색을 하면 되겠다 라고 생각을 했지만

백준 첫 번째 예시에서 (0, 4) 좌표를 기준으로 생각했을 때 위의 가정이 틀렸다는 것을 금방 깨달을 수 있었다.

앞선 (0, 4) 좌표의 경우 자기 자신의 오른쪽과 아래만 봐야 하고 왼쪽은 왔던길이므로 탐색하면 안되는데 1 로 설정해주지않으면 왼쪽의 값(10) 까지 보게 되면서 앞으로만 이동하지 않고 뒤로도 왔다갔다 하며 무한히 탐색하게 된다.

 

BFS 활용 문제를 처음 풀어보는 터라 여기저기서 참고도 많이 했는데 아직도 한번에 안되는 부분들이 많다.

기초 코드는 확실하게 보고 넘어왔다고 생각했는데 역시 아직도 멀었다.