SWEA 1249. 보급로(Python)(D4)

swea, 1227번 미로문제를 응용하는 BFS문제이다.
기본적으로 bfs는 방문처리를 하는 visit배열과 주어진 list 배열 2가지를 이용하는데,
여기서는 효율성(최소복구비용)을 따져야 하므로 time 배열을 하나 추가했다.
즉, 아래에서
li배열 -> 해당 x,y지역을 복구하는데 드는 시간
time배열 -> 해당지역에 도착해 복구하는데 드는 최소 총 시간
visit배열 -> 방문처리

• 출발점에서 시작해 상하좌우로 탐색한다. nx=x+dx, ny=y+dy
• 만약, 방문하지 않은 지역일 경우,
  - 해당지역 방문처리 및, 해당지역의 time배열 갱신(li[nx][ny]+time[x][y])
• 이미 방문을 했었지만 time[nx][ny]>li[nx][ny]+time[x][y]일 경우
  - 새로운 time으로 갱신
  최종적으로 time[nx][ny] 리턴

어떻게 보면 동적계획법도 들어가 있다고 볼수있다(time 배열)

from collections import deque
res=[]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
for m in range(int(input())):
    tmp=0
    N=int(input())
    li=[[0]*(N+1)]
    for i in range(N):
        li.append([0]+list(input()))
    visit=[[0]*(N+1) for i in range(N+1)]
    time=[[0]*(N+1) for i in range(N+1)]
    q=deque()
    q.append((1,1))
    visit[1][1]=1
    time[1][1]=int(li[1][1])
    while q:
        x,y=q.popleft()
        now_time=int(time[x][y])
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<nx<=N and 0<ny<=N:
                if visit[nx][ny]==0 or now_time+int(li[nx][ny])<time[nx][ny]:
                    q.append((nx,ny))
                    visit[nx][ny]=1
                    time[nx][ny]=now_time+int(li[nx][ny])
    tmp=time[N][N]
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))