[이코테 Ch5-4] 미로탈출 (BFS)

👩🏻‍💻문제설명

[이코테 Ch5-4] 미로탈출 (BFS)

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

✍️Idea Sketch

알고리즘 : BFS

시간복잡도

2차원 맵에서 상하좌우 4방향으로 움직일 수 있고, 특정 목표정점까지의 최단거리를 구할 때, BFS 탐색 방법을 사용하게 될 경우 시간복잡도는 O(NM)이다. 정점의 개수가 O(NM)개이고, 각 정점에서 연결된 간선이 4개씩이니까 간선의 총 개수는 O(4NM)인데, 상수배는 무시할 수 있으므로 똑같이 O(NM)으로 쓸 수 있다. BFS 탐색 과정에서 정점을 O(NM)개 보고 간선도 O(NM)개 보니 O(NM+NM) = O(2NM)인데, 역시 상수배는 무시할 수 있으니 O(NM)이다.

백준 참고 사이트

✍️내 소스코드

• 출발지 (0, 0)에서 출발하여 목적지 (n-1, m-1)까지 미로를 탐색한다.
• 이동하려는 좌표 (nx, ny)의 좌표값이 1로 괴물이 없는 경우, 해당 좌표값을 갱신하고 queue에 좌표를 추가한다.
• 최종적으로 목적지 (n-1, m-1)의 좌표값을 리턴한다.

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


  def bfs():
    queue = deque([[0, 0]])

    while queue:
      x, y = queue.popleft()
      for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
        nx, ny = x + dx, y + dy
        if (0 <= nx < n) and (0 <= ny < m) and graph[nx][ny] == 1:
          graph[nx][ny] = graph[x][y] + 1
          queue.append([nx, ny])

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


  n,m = map(int, si().split())
  graph = [list(map(int, si().rstrip())) for _ in range(n)]

  print(bfs())