[Python][이코테] 미로 탈출

문제

동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력 조건

• 첫째 줄에 두 정수 N, M (4 ≤ N,M ≤ 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 또는 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

 

문제 해설

이 문제는 BFS로 큐를 이용하여 풀 수 있다.

 

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]

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 == -1 or nx == n or ny == -1 or ny == m:
        continue
        
      if graph[nx][ny] == 0:
        continue

      if graph[nx][ny] == 1:
        queue.append((nx, ny))
        graph[nx][ny] = graph[x][y]+1

  return graph[n-1][m-1]
  
print(bfs(0,0))

8~9 행 dx, dy에 현재 좌표 기준 움직일 예정인 상대좌표값

(-1, 0), (1, 0), (0,-1), (0, 1) - 상, 하, 좌, 우 값을 저장

 

33행 - 무조건 처음은 1로 시작하며 처음부터 끝으로 가기 때문에 bfs(0,0)으로 함수 실행

 

이후 def bfs(x, y)에서

 

queue에 들어가는 값 - 현재 좌표

nx, ny - 다음에 갈 예상 위치 (상하좌우)

-1 or n, m - 주어진 값의 범위를 벗어난 위치

graph[nx][ny] == 0 - 해당 위치 접근 불가

graph[nx][ny] == 1 - 해당위치 이동 가능

 

일부러 어려운 예를 들어서 보면은

5 5
10000
11111
10010
10011
11101

1.

 

queue = [(0,0])

1	0	0	0	0
1	1	1	1	1
1	0	0	1	0
1	0	0	1	1
1	1	1	0	1

2.

queue = [(1,0)]

1	0	0	0	0
2	1	1	1	1
1	0	0	1	0
1	0	0	1	1
1	1	1	0	1

3.

queue = [(0,0), (2,0), (1,1)]

3	0	0	0	0
2	3	1	1	1
3	0	0	1	0
1	0	0	1	1
1	1	1	0	1

4.

queue = [(3,0), (1, 2)]

3	0	0	0	0
2	3	4	1	1
3	0	0	1	0
4	0	0	1	1
1	1	1	0	1

5.

queue = [(4,0), (1,3)]

3	0	0	0	0
2	3	4	5	1
3	0	0	1	0
4	0	0	1	1
5	1	1	0	1

 

이러한 과정을 거쳐 결국 완성되는 표는

 

3	0	0	0	0
2	3	4	5	6
3	0	0	6	0
4	0	0	7	8
5	6	7	0	9

 

따라서 마지막에 graph[n-1][m-1]을 출력하면 9 가 나오게 되는 것이다.