[이코테]미로 탈출 / [백준]2178번: 미로 탐색

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

2178번: 미로 탐색

---

from collections import deque

#미로 정보 입력받기
n, m = map(int,input().split())

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


#상하좌우 좌표
dx=[-1,1,0,0]
dy=[0,0,-1,1]

#(0,0) 시작점으로 bfs 수행

q=deque()
q.append((0,0))

while q:
  x,y = q.popleft()
  #상하좌우 인접한 칸 체크
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    #nx, ny가 미로 범위를 벗어나지 않고, 방문한 적 없는 노드일 때
    if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1:
      graph[nx][ny] = graph[x][y] + 1
      q.append((nx,ny))

print(graph[n-1][m-1])

bfs로 수행하되, 방문 처리와 칸의 개수 count를 동시에 해주면 된다!

 

예를 들어 이렇게 생긴 미로가 있다고 가정하자.

1	0	0
1	1	1
0	0	1

시작점 (0,0)에서의 이동 칸의 개수는 1이다.

인접한 칸 중 방문 가능한 칸은 (1,0)인데, ((1,0)까지의 이동 칸의 개수)는 ((0,0)까지의 이동 칸 개수) + 1 =2이다.

(1,0)을 시작점으로 bfs를 또다시 수행하면 (1,1)을 방문할 수 있다.

(1,1)까지의 이동 칸의 개수는 ((1,0)까지의 이동 칸의 개수) + 1 = 3이다.

이런식으로 bfs를 수행하면서 이동 칸의 개수를 update해주면 방문처리와 이동 칸 개수 세는 일을 한 번에 해결할 수 있다.

 

graph[i][j]==0이면 방문할 수 없는 칸

graph[i][j]==1이면 방문한 적 없는 칸이다. --> update해주기

graph[i][j]>1이면 방문 처리된 칸이다.