BOJ 2178. 미로탐색

hidden_·2021년 6월 30일
0

코딩테스트

목록 보기
8/10

미로탐색 바로가기

BFS를 사용하여 해결,,
처음엔 DFS로 풀려다가 DFS는 최단경로임을 보장할 수 없다는 것을 까먹음,.
어떻게 이걸 까먹을 수 있을까 싶으면서
꾸준히 해야하는 것의 중요성을 다시한번 깨닫는 순간😥

import sys
from collections import deque
global N
global M
global data
N, M = map(int, sys.stdin.readline().rstrip().split(' '))
data = [list(input()) for i in range(N)]
visit = [[0 for i in range(M)] for j in range(N)]


def BFS(x, y, visit):
   queue = deque()
   queue.append([x, y])
   #상, 우 , 하, 좌
   dx = [0, 1, 0, -1]
   dy = [-1, 0, 1, 0]
   visit[x][y] = 1
   while queue:
       [x, y] = queue.popleft()
       if x == N-1 and y == M-1:
           return visit[x][y]
       for i in range(4):
           nx = x + dx[i]
           ny = y + dy[i]
           if 0 <= nx <= N-1 and 0 <= ny <= M-1 and data[nx][ny] == "1" and visit[nx][ny] == 0:
               queue.append([nx, ny])
               #변화된 좌표까지의 최단 길이 
               visit[nx][ny] = visit[x][y]+1

print(BFS(0, 0, visit))

visit은 해당 좌표까지 가장 짧은 경로의 길이를 담고 있음

profile
steady

0개의 댓글