[BOJ] 백준 2178 미로 탐색

태환·2024년 1월 29일
0

Coding Test

목록 보기
25/151

📌 [BOJ] 백준 2178 미로 탐색

📖 문제

📖 예제

📖 풀이

from collections import deque

N, M = map(int, input().split())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
graph = []
for _ in range(N):
  graph.append(list(map(int, input())))
  
def BFS(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 nx>=N or ny<0 or ny>=M:
        continue
      elif graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx,ny))

BFS(0,0)
print(graph[-1][-1])

미로 탐색 문제는 BFS를 이용한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글