[백준] 택배

https://www.acmicpc.net/problem/1719

1719번: 택배

1. 문제 이해

모든 집하장간의 최단 경로로 이동하는 경로에 가장 먼저 방문해야하는 지점을 찾는 문제입니다.

2. 문제 접근

첫번째 접근: 플로이드 와샬

모든 집하장간의 최단 경로를 찾아야 하기에 플로이드 와샬을 먼저 떠올렸습니다. 제가 문제를 처음 읽었을 때 놓쳤던 부분이 가장 먼저 방문해야하는 지점인데 가장 마지막 지점을 출력하고 있어서 틀렸었습니다. 가장 먼저 방문해야하는 지점을 찾는 것은 간단한데 플로이드 와샬은 i ~ k, k ~ j를 이어보는 과정이기 때문에 만약 i ~ k, k ~ j가 더 최소 경로이면 i ~ k로 갈때 가장 먼저 방문하는 집하장이 i ~ j를 이동하는데 가장 먼저 방문하는 지점이 되게 됩니다.

3. 풀이

import sys, math
from collections import defaultdict, deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

INF = 200000

dist = [
    [INF] * (n + 1)
    for _ in range(n + 1)
]

ans = [
    [j for j in range(n + 1)]
    for i in range(n + 1)
]


for _ in range(m):
    a, b, w = tuple(map(int, input().split()))
    dist[a][b] = w
    dist[b][a] = w


for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                ans[i][j] = ans[i][k]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            print('-', end=' ')
        else:
            print(ans[i][j], end=' ')

    print()

4. 회고

문제가 쉬워보인다고 생각해 문제 이해 단계를 소홀이 하여 불필요한 오답 코드를 작성했습니다. 문제 이해 단계를 소홀히 하지 않게 더 조심하겠습니다.