[Python] 2178번 미로 탐색

✏️ 문제

 

문제 파악

최소의 칸 수를 출력하기 원하므로 전체 경로를 탐색하는 DFS가 아닌 BFS를 사용해야 한다. 또한 상하좌우로 움직일 수 있으므로 상하좌우 하나하나 움직이며 움직인 좌표가 이동할 수 있는 칸인 지, 이미 방문했던 칸은 아닌 지 확인하는 것이 포인트이다.

 

처음에는 단순히 지나간 칸마다 cnt += 1을 해서 cnt 값을 출력하는 방식으로 문제를 풀었다. 그런데 생각해보니 지나간 칸이더라도 그 이후에 갈 수 있는 경로가 없다면 그 칸을 문제에서 요구하는 최소 칸 수에 포함시키면 안 된다. 그래서 이전의 방문한 칸에 이때까지 지나왔던 칸의 수를 1씩 더하니 답이 나왔다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
graph = [input() for _ in range(n)]
visited = [[0] * m for _ in range(n)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs():    
  visited[0][0] = 1
  q = deque()
  q.append((0, 0))

  while q:
    x, y = q.popleft()

    for i in range(4):
      nx = x + d[i][0]
      ny = y + d[i][1]
      
      if (0 <= nx < n and 0 <= ny < m) and graph[nx][ny] == '1' and visited[nx][ny] == 0:
        visited[nx][ny] = visited[x][y] + 1
        q.append((nx, ny))

bfs()
print(visited[n-1][m-1])