⏹️[SW Expert Academy] [Python] [D4] [1249] 보급로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&problemLevel=5&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=5&pageSize=10&pageIndex=1

SW Expert Academy

풀이

# 1249. [S/W 문제해결 응용] 4일차 - 보급로
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x, y):
    q = deque([(x,y)])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if dist[x][y] + graph[nx][ny] < dist[nx][ny]: // 다음 가야할 거리가 지금까지 거리 + 그래프의 크기 보다 큰 경우
                    dist[nx][ny] = dist[x][y] + graph[nx][ny]
                    q.append((nx, ny))

for test_case in range(1, int(input())+1):
    N = int(input())
    graph = [list(map(int, input())) for _ in range(N)]
    dist = [[1e9]*N for _ in range(N)]
    dist[0][0] = graph[0][0]

    bfs(0,0)
    print("#{} {}".format(test_case, dist[N-1][N-1]))

BFS와 다익스트라 등을 이용해서 푸는 여러가지 방법이 존재한다. 나는 BFS가 가장 편한 방법이어서 사용했다.