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를 떠올리는 방식으로 공부를 해보려고 한다
'알고리즘 문제 풀이 > 이코테' 카테고리의 다른 글
[이코테] CH05 DFS/BFS 실전문제 16번 연구소 (1) | 2023.12.01 |
---|---|
[이코테] CH05 DFS/BFS 실전문제 15번 특정 거리의 도시 찾기 (0) | 2023.11.27 |
[이코테] CH05 DFS/BFS 실전문제 3번 음료수 얼려 먹기 (0) | 2023.11.27 |
[이코테] CH04 구현 실전문제 14번 외벽 점검 (0) | 2023.11.27 |
[이코테] CH04 구현 실전문제 13번 치킨 배달 (0) | 2023.11.27 |