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

import sys

sys.stdin = open("input/1249_input.txt", "r")

T = int(input())

INF = 10**5


def bfs(si, sj, ei, ej):
    q = []
    v = [[INF] * N for _ in range(N)]

    q.append((si, sj))
    v[si][sj] = arr[si][sj]

    while q:
        ci, cj = q.pop(0)

        # 네 방향, 범위 내 중복 허용 (이동할 위치보다 더 적은 비용만)
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = ci + di, cj + dj

            if 0 <= ni < N and 0 <= nj < N and v[ni][nj] > v[ci][cj] + arr[ni][nj]:
                q.append((ni, nj))
                v[ni][nj] = v[ci][cj] + arr[ni][nj]

    return v[ei][ej]


for case in range(1, T + 1):
    N = int(input())

    arr = [list(map(int, input())) for _ in range(N)]

    ans = bfs(0, 0, N - 1, N - 1)

    print(f"#{case} {ans}")

풀이.

https://www.youtube.com/watch?v=SpK-4cRlUfg
해당 강의 영상을 보고 해결했다.
처음에는 단순히 DFS 알고리즘으로 해결하려고 했으나, 이러한 경우 시간 초과가 발생하고, 때문에 BFS 알고리즘으로 해결해야 한다.

BFS 알고리즘에 자신이 없어서, 강의 영상을 보고 이해한 바로
시작 위치를 처음 큐에 넣어준다.
그리고 해당 큐가 비어있지 않은 경우, 첫번째 좌표를 pop 해서, 그 좌표에 상하좌우로 비용을 확인하고, 움직일 곳의 미리 들어있는 비용이 현재 위치의 비용과 다음 위치에 필요한 비용의 값보다 큰 경우, 해당 비용을 업데이트 해준다.

이렇게 처리하면, 비용이 가장 작은 값이 목적지에 존재하게 된다.