[Algorithm] 미로찾기 (BFS)

from collections import deque

n, m = map(int, input().split())
graph = []
result = 0

queue = deque()

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


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

# 첫번째: 큐에 삽입하고 방문처리하기
# 두번째부터: 큐에 있는 것 하나 빼서 방문하지 않은 것 있으면, 🖐🏼모두🖐🏼 큐에 넣고 방문처리하기
def bfs(x, y):
    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 ny < 0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1 # 이 문제의 result 구하는 방식은 거리를 모두 더해놓고 맨 마지막 대상을 빼는게 정답임
                # 큐에 넣기
                queue.append((nx, ny))
    return graph[n-1][m-1]

print(bfs(0, 0))

초반에 혼자 풀려고 정답 안보고 2시간 정도 고민함 (어제, 오늘 ㅋ)

 

(1, 1) 부터 (n, m) 까지 길은 무조건 뚫려있다는 전제 하에, 최소거리를 구해야 하는데

처음에는 그럼 무조건 (상, 하, 좌, 우)만 가면 되겠네 해서 if, else 케이스를 생각하려 했음. 

그 직전에 DFS 기반 문제를 풀어서 그런지 DFS (재귀) 식으로 되는건가 하고 때려봤음 (음?)

 

고민 끝에 해답을 보면서 분석하기로 했는데 분석 결과, 왜 BFS 아이디어를 쓸 수 밖에 없는지를 떠올리는게 관건이었음.

 

근데 이렇게 한 방향만 구하면 안되는 문제였음.

모든 경우의 수를 다 따진 다음 최소거리를 구해야 하는 문제임.

 

우선 항상 result를 어떻게 도출해낼 것인지가 관건임.

 

result를 구하는 방식

: 다음 노드로 넘어갈 때 그 전에 있는 노드에 +1을 해주는 방식

 

모든 경우의 수 따지는 방법

: 처음 노드 부터 (상, 하, 좌, 우) 를 모두 탐색해봐야 함. -> BFS (순차대로 모두 따지는 방법)

case 1) 0인 경우 PASS

case 2) 경로가 아닌 경우 PASS

case 3) 1, 2가 아닌 경우 즉, 경로이면서 1인 경우

-> result를 구하는 방식 (그 전 노드에 +1 해주기) 사용 / BFS로 풀 예정이므로 Queue에 넣어주기