[이코테] CH05 DFS/BFS 실전문제 4번 미로탈출

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9

def BFS(graph):

    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    queue = deque()
    queue.append((0,0))
    while queue:
        x,y = queue.popleft()
        if x == N-1 and y == M-1:
           return graph[x][y]
        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 graph[nx][ny] == 1:
            graph[nx][ny] = graph[x][y] + 1
            queue.append((nx,ny))

N,M = map(int,sys.stdin.readline().split())
graph = []
for i in range(N):
    graph.append(list(map(int,sys.stdin.readline().rstrip())))

print(BFS(graph))

딱 보자마자 모든 거리를 가는거보단

최단거리를 계산하는 것이므로 

 

BFS를 이용하는게낫다고 생각했다

DFS로 깊게 팠는데

만약 최단거리가 가장 나중에 선택되는 방법이라면

시간낭비가 심한것이 이유이다.

 

대다수 BFS가 시간복잡도 면에서 우수하므로

최대한 문제를 BFS로 풀려고 노력해보고

안되면 DFS를 떠올리는 방식으로 공부를 해보려고 한다