SW Expert Academy 1249번 보급로 | Python
🔎 문제 설명
💙 D4
- 난이도 ★★☆☆ - 그래프탐색 BFS
보자마자 그래프탐색이 떠올랐다. 문제는 길을 메우는 데 걸리는 시간을 어떻게 처리해줄 것인가로, (nx, ny)까지 기존에 걸렸던 시간과 이전 위치 (x,y)에서 (nx,ny)까지의 거리를 비교해서 더 작은 값으로 대체해주었다.
💻 내 코드
from collections import deque
T = int(input())
for t in range(T):
N = int(input())
maps = [list(map(int, list(input()))) for _ in range(N)]
def bfs(map_size):
queue = deque([(0,0)])
visited = [[float('inf') for _ in range(N)] for _ in range(N)]
visited[0][0] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<N and 0<=ny<N:
tmp = visited[x][y] + maps[nx][ny]
if tmp < visited[nx][ny]:
queue.append((nx,ny))
visited[nx][ny] = tmp
return visited[map_size-1][map_size-1]
print(f'#{t+1}',bfs(N))
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).