SW Expert Academy 1249. [S/W 문제해결 응용] 4일차 - 보급로

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE

SW Expert Academy

이 문제는 너비 우선 탐색(bfs)을 사용하여 해결하였다. collections모듈에서 deque를 사용하여 해결했다. queue에는 현재의 위치에서 동서남북을 탐색하여서 만약 거리가 줄어들었다면 queue에 다시 넣어서 탐색을 하도록 하였다. 나의 코딩은 다음과 같다.

from collections import deque
def solution(map1):
    l=len(map1)
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    d=[[float('inf') for _ in range(l)] for _ in range(l)]
    d[0][0]=int(map1[0][0])
    queue=deque()
    queue.append([0,0])
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if -1<nx<l and -1<ny<l and d[nx][ny]>d[x][y]+int(map1[nx][ny]):
                d[nx][ny]=d[x][y]+int(map1[nx][ny])
                queue.append([nx,ny])
    return d[l-1][l-1]


t=int(input())
for test in range(1,t+1):
    n=int(input())
    map1=[]
    for _ in range(n):
        map1.append(input())
    answer=solution(map1)
    print('#{} {}'.format(test,answer))