미로 탈출

문제

출처 : 실전문제, 이것이 코딩테스트다 with 파이썬

풀이

from collections import deque

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

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

# 상하좌우 나타내기
dx = [-1,1, 0, 0]
dy = [0,0,-1,1]

def solve(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 < 0 or ny <0 or nx >=n or ny >=m:
        continue
      # 만약 벽이면 무시하기
      if maze[nx][ny] == 0:
        continue
      # 만약 갈 수 있는 길이면 최단 거리 기록하기
      if maze[nx][ny] == 1:
        maze[nx][ny] = maze[x][y] + 1
        queue.append((nx,ny))
  # 도착한 최단 거리 출력하기
  return maze[n-1][m-1]

print(solve(0,0))

후기

본 문제는 BFS를 바로 체험해볼 수 있는 문제라고 한다. 전체적인 원리도 이해가고, 어떻게 해야 할지는 알겠지만, 역시 어떤 경우에 BFS를 사용해야 할지를 모르겠다. 해당 부분은 조금 더 코드를 작성해보고, 연습해서 BFS와 DFS를 구분하여 적을 수 있는 경우를 확인해봐야 겠다.