[백준] 1719 택배

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

모든 집하장에 대하여 다른 집하장으로 이동하는 최소 소요시간을 구하여야 했습니다.

플로이드 워셜 알고리즘을 이용하여 모든 집하장에 대해 이동 최소 시간을 구하도록 하였고, 다른 집하장으로 이동시 가장 먼저 이동해야할 집하장을 기록하기 위하여 2차원 배열을 이용하였습니다.

 

우선적으로 주어진 경로들은 서로 연결되어 있으므로 가장 먼저 이동할 집하장으로 도착 집하장 번호를 기록하였습니다.

이후 플로이드 워셜 알고리즘을 이용할 때, 중간에 다른 집하장을 거쳐 이동하는 것이 더 빠른 경우가 있어 조건이 필요했습니다.

이러한 경우에는 중간에 거치는 집하장으로 가는 경로에 대해서 가장 먼저 이동하는 집하장을 가져와 기록하였습니다.

2) 알고리즘

• 플로이드 워셜

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())                   # 집하장 수, 경로 수
dp = [[1e10] * N for _ in range(N)]                             # 두 집하장간 최단 경로
answer = [['-'] * N for _ in range(N)]                          # 먼저 이동해야하는 집하장 번호

for _ in range(M):
    a, b, t = map(int, sys.stdin.readline().split())            # 집하장 a, b, 이동 시간
    a -= 1                  
    b -= 1
    dp[a][b], dp[b][a] = t, t                                   # 두 집하장 이동에 소요되는 시간
    answer[a][b], answer[b][a] = b, a                           # 먼저 이동해야하는 집하장 번호 기록

for k in range(N):                                              # 중간에 거치는 집하장
    for i in range(N):
        for j in range(N):
            # i, j, k 가 모두 다르며, 중간에 k 집하장을 거쳐 가는게 더 빠를때
            if i != j != k and dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]                  # 최소 시간 갱신
                answer[i][j] = answer[i][k]                     # 처음 이동할 집하장이므로
                                                                # i에서 k로 이동시 처음 이동하는 집하장 기록

for i in range(N):                          # 출력
    for j in range(N):
        if answer[i][j] == '-':
            print('-', end=' ')
        else:
            print(answer[i][j]+1, end=' ')
    print()

---

🔗 문제 링크

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

1719번: 택배

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다