보급로

첫번째 풀이

from collections import deque
answer = []


def init():
    answer.clear()


def dijkstra():
    global answer
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    INT_MAX = 987654321
    q = deque()
    start = (0, 0)
    q.append(start)

    dist = [[INT_MAX for _ in range(N)] for _ in range(N)]
    dist[0][0] = 0

    while q:
        curX, curY = q.popleft()
        for xx, yy in zip(dx, dy):
            nxtX, nxtY = curX + xx, curY + yy
            if 0 <= nxtX < N and 0 <= nxtY < N:
                if nxtX == N-1 and nxtY == N-1:
                    answer.append(dist[curX][curY])

                if dist[nxtX][nxtY] > dist[curX][curY] + graph[nxtX][nxtY]:
                    q.append((nxtX, nxtY))
                    dist[nxtX][nxtY] = dist[curX][curY] + graph[nxtX][nxtY]


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    init()
    N = int(input())
    graph = [[] for _ in range(N)]
    for i in range(N):
        temp = input()
        for item in temp:
            graph[i].append(int(item))

    dijkstra()
    print("#" + str(test_case) + " " + str(min(answer)))

두번째 풀이

import heapq

answer = []


def init():
    answer.clear()


def dijkstra():
    global answer
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    INT_MAX = 987654321
    q = []
    start = (0, 0)

    dist = [[INT_MAX for _ in range(N)] for _ in range(N)]
    dist[0][0] = 0

    heapq.heappush(q, [dist[0][0], start])

    while q:
        curDist, curPos = heapq.heappop(q)
        for xx, yy in zip(dx, dy):
            nxtX, nxtY = curPos[0] + xx, curPos[1] + yy
            if 0 <= nxtX < N and 0 <= nxtY < N:
                if nxtX == N-1 and nxtY == N-1:
                    answer.append(dist[curPos[0]][curPos[1]])

                if dist[nxtX][nxtY] > dist[curPos[0]][curPos[1]] + graph[nxtX][nxtY]:
                    heapq.heappush(q, [dist[nxtX][nxtY], [nxtX, nxtY]])
                    dist[nxtX][nxtY] = dist[curPos[0]][curPos[1]] + graph[nxtX][nxtY]


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    init()
    N = int(input())
    graph = [[] for _ in range(N)]
    for i in range(N):
        temp = input()
        for item in temp:
            graph[i].append(int(item))

    dijkstra()
    print("#" + str(test_case) + " " + str(min(answer)))

세번째 풀이

import heapq

def dijkstra():
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    INT_MAX = 987654321
    q = []
    start = (0, 0)

    dist = [[INT_MAX for _ in range(N)] for _ in range(N)]
    dist[0][0] = 0

    heapq.heappush(q, [dist[0][0], start])

    while q:
        curDist, curPos = heapq.heappop(q)

        for xx, yy in zip(dx, dy):
            nxtX, nxtY = curPos[0] + xx, curPos[1] + yy
            if 0 <= nxtX < N and 0 <= nxtY < N:
                if dist[nxtX][nxtY] > dist[curPos[0]][curPos[1]] + graph[nxtX][nxtY]:
                    heapq.heappush(q, [dist[nxtX][nxtY], [nxtX, nxtY]])
                    dist[nxtX][nxtY] = min(dist[nxtX][nxtY], dist[curPos[0]][curPos[1]] + graph[nxtX][nxtY])

    return dist[N-1][N-1]


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    graph = [[] for _ in range(N)]
    for i in range(N):
        temp = input()
        for item in temp:
            graph[i].append(int(item))

    result = dijkstra()

    print("#" + str(test_case) + " " + str(result))

---

D4

그래프 안에서 각 노드 안에 가중치가 적혀있고, 최적의 경로로 움직이는 전형적인 dijkstra, 혹은 bfs 문제라고 생각이 들었다.

첫번째 풀이는 사실 bfs와 dijkstra의 차이점을 명확히 알지 못하고 푼 것이다.
dijkstra 는 heapq, 즉 최소힙 자료구조를 활용하여 매번 최소거리의 데이터를 꺼내 연산을 진행한다.
반면 bfs는 그런 것은 신경쓰지 않고 상하좌우와 경계값만 판단하여 모든 노드를 탐색한다.
따라서 최소거리의 데이터부터 뽑아 진행하는 dijkstra의 수행시간이 더 빠를 수 밖에 없다.

그래서 두번째 풀이는 heapq 최소힙 자료구조를 사용해 최적화 하였다.

마지막 세번째 풀이는 굳이 global 변수 answer를 두지 않고 결과값을 구할 수 있을 것 같아 수정해보았다.
dist 배열에 저장되는 값을 항상 전에 있는 값과 새롭게 할당되는 값을 비교하여 더 작은 값으로 넣게 되면, 모든 연산 후 dist[N-1][N-1] 에 저장된 값이 최소임을 보장할 수 있다.

Dijkstra 최단거리 알고리즘을 복습해 볼 수 있는 좋은 문제였다.

---

출처: https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYj2mga6ZewDFASl&contestProbId=AV15QRX6APsCFAYD&probBoxId=AYj2mga6Ze0DFASl&type=PROBLEM&problemBoxTitle=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+Track+%28%EB%82%9C%EC%9D%B4%EB%8F%84+%EC%83%81%29&problemBoxCnt=6