https://www.acmicpc.net/problem/2178
import sys
from collections import deque
input = sys.stdin.readline
def bfs():
pos = [0,0]
discoverd = deque([pos])
while discoverd:
if pos == [N-1,M-1]:
break
pos = discoverd.popleft()
maze[pos[0]][pos[1]] = 0
dx_pos = [[pos[0],pos[1]-1],[pos[0],pos[1]+1],[pos[0]-1,pos[1]],[pos[0]+1,pos[1]]]
# 상하좌우 아래 for문에 때려 박을 수도 있지만 한개코드가 길어보여서 그냥 만듬
for i in dx_pos:
if 0 <= i[0] < N and 0<=i[1]<M and i not in discoverd and maze[i[0]][i[1]]:
discoverd.append(i)
least_dis[i[0]][i[1]] = least_dis[pos[0]][pos[1]] + 1
return least_dis[N-1][M-1]
N, M = map(int,input().split())
maze = [list(map(int,input().strip())) for _ in range(N)]
least_dis = [[0]*M for _ in range(N)]
print(bfs()+1)
bfs를 사용해서 최단거리를 구해줬다. 어떤 곳으로 가든 가중치가 똑같고 상태가 변하지 않아서 bfs를 사용했다.
중간에 bfs의 최단거리를 어디서 더해줘야하는지 고민하다가 도움을 받아서 least_dis라는 리스트를 하나 더 만들어서 각 좌표의 최소이동 거리를 구했다. 마지막에 +1을 한 이유는 0,0일 때도 거리가 1로 시작하기 때문에 1을 더해줬다.
'백준 문제 풀이 및 피드백' 카테고리의 다른 글
2023.01.16 백준 DFS와 BFS (0) | 2023.01.16 |
---|---|
2023.01.15 반복수열 백준(Python) (0) | 2023.01.15 |
2023.01.15 영역구하기 백준 (0) | 2023.01.15 |
2023.01.15 단지번호붙이기 백준 (0) | 2023.01.15 |
2023.01.14 백준 바이러스 (0) | 2023.01.14 |