BFS 문제 (미로 탈출) - 이것이 코딩테스트다

BFS 문제 (미로 탈출) - 이것이 코딩테스트다

 

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

 

입력 조건

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

출력 조건

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

 

입력 예시 5 6 101010 111111 000001 111111 111111

출력 예시 10

 

이 문제는 최소 칸의 개수를 구하는 문제이다. DFS로는 최소 칸의 개수를 구할 수 있을까? 필자가 보기에는 힘들어 보인다. 깊이 우선 탐색이기 때문에 최소와 상관없이 깊이를 우선적으로 탐색할 것이기 때문이다. 그래서 이런 유형의 문제는 BFS를 이용한다. BFS를 이용하면 너비 우선 탐색이기 때문에 천천히 모든 곳을 탐색하게 된다. 첫번째 아이디어는 BFS로 시작한다.

 

문제를 BFS로 풀어야겠다는 것은 알겠다. 그렇다면 어떤 식으로 구현해야 할까?

문제에서 처음은 (1,1)부터 시작한다고 명시되어있기 때문에 이곳부터 (x-1,y), (x+1,y), (x,y-1), (x,y+1)이동한 값을 기존의 값에 +1을 해주면 된다. 큐를 이용하여 이 좌표들을 넣는다면, 큐에 들어간 것들부터 탐색이 되기 때문에 순차적으로 각각의 길에 대한 거리를 알 수 있다. 

 

코드로 확인해보자.

from collections import deque

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

graph = []
for i in range(n):
  graph.append(list(map(int,input())))
  
def bfs(x,y):
  queue = deque()
  queue.append((x,y))
  
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]
  
  while queue:
    x,y = queue.popleft
  
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
    
      if nx <=-1 or ny <=-1 or nx >=n or ny >=m:
        continue
      if graph[nx][ny] == 0:
        continue
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx,ny))
  return graph[n-1][m-1]

print(bfs(0,0))
  

문제는 1,1부터 시작한다고 했는데, 왜 print안에는 0,0이 들어갈까? 문제에서 1,1은 실제 배열에서의 0,0과 같다. 배열은 인덱스 0부터 시작하기 때문이다. 그래서 실제 최소거리를 알기 위해서는 0,0을 집어넣는 것이 올바르다.