[DFS/BFS] 이코테 (파이썬) 미로 탈출 풀이

[문제]

동빈이는 N * M 크기의 직사각형 형태의 미로에 갇혔습니다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 합니다.

 

동빈이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있습니다.

 

이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있습니다. 미로는 반드시 탈출할 수 있는 형태로 제시됩니다.

 

이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하세요. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 

 

모함해서 계산합니다.

 

[입력 조건]

1. 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로

 

    미로의 정보가 주어집니다. 각각의 수들은 공백 없이 붙어서 입력으로 제시됩니다. 또한 시작칸과 마지막칸은 항상 1입니다.

 

[출력 조건]

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

<입력 예시>
5 6
101010
111111
000001
111111
111111
<출력 예시>
10

 

[풀이]

from collections import deque

def bfs(i, j) :
  queue = deque()
  queue.append((i, j))

  while queue :
    i, j = queue.popleft()

    for k in range(4) :
      result_x = i + go_x[k]
      result_y = j + go_y[k]

      if result_x<0 or result_x>=n or result_y<0 or result_y>=m :
        continue

      if graph[result_x][result_y] == 0:
        continue
        
      if graph[result_x][result_y] == 1 :
        graph[result_x][result_y] = graph[i][j] + 1
        queue.append((result_x, result_y))

  return graph[n-1][m-1]

n, m = map(int, input().split())

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

go_x = [-1, 1, 0, 0]
go_y = [0, 0, -1, 1]

print(bfs(0, 0))

 

우선적으로 반복문을 통해 graph에 값을 입력받아 2차원 리스트를 형성하고

특정 위치에서 이동할 상, 하, 좌, 우 방향을 정의한다.

 

bfs( ) 메소드에서는 큐를 사용하기 위해 deque 라이브러리를 사용하도록 하고 초기에 i 값과 j 값으로 이루어진

 

튜플데이터를 담는다. 그 후 큐가 빌 때까지 반복문을 수행한다.

 

반복문을 수행할 때마다 하나의 원소를 꺼낸 후 현재 위치에서 상, 하, 좌, 우 방향으로의 위치를 확인한다.

 

만약 확인하는 그 위치가 미로 찾기 공간을 벗어난다면 무시하도록 하고 해당 위치가 괴물에 해당하는 값인 0일 때도

 

무시하도록 한다.

 

만약 해당 위치가 이동할 수 있는 값인 1이라면 해당 위치를 처음 방문하는 경우에만 최단 거리를 기록하고

 

바로 직전 위치에서의 최단 거리 값에서 1을 더한 값을 할당한다. 또한, 다음으로 이동할 위치까지는 1만큼 거리가 더 

 

먼 곳이기 때문에 큐에 데이터를 넣어줌으로써 거리 값을 1 증가시킬 수 있다.

 

최종적으로 가장 오른쪽 아래까지의 최단 거리를 반환하여 바로 출력할 수 있도록 한다.

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저