[백준/2178/파이썬] 미로탐색

소스코드

from collections import deque

N, M = map(int, input().split())

graph = []

for _ in range(N):

  graph.append(list(map(int, input())))

def bfs(x, y):

  dx = [-1, 1, 0, 0] 

  dy = [0, 0, -1, 1]

  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 nx >= N or ny < 0 or ny >= M:  # 위치가 벗어나면 안됨

        continue

      if graph[nx][ny] == 0:          # 벽은 이동 X

        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))

알고리즘

DFS는 스택 !!! BFS는 큐 !!!

이번 문제도 무난한 BFS 문제였다.

좌표 하나를 가지고 그 주위를 탐색하며 큐에 넣고 빼고를 반복하는 알고리즘입니다.

하지만 신경 써줘야 할 부분이 있었는데 벽을 넘어가면 index Error가 나오기 때문에

그 크기에 대한 설정을 continue를 사용해서

1. 초기 설정해준 맵의 크기를 벗어나지 않는다.

2. 벽은 이동할 수 없다.

두 조건을 만족하면 이동하였습니다.

 

1번 예시로 실행을 하면 다음과 같이 맵의 숫자가 바뀌는데 최종 (N,M)의 값이 답이 되겠죠 ~?