새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 1719 택배

by 언호 2022. 7. 18.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 택배

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 2206 벽 부수고 이동하기  (0) 2022.08.15
[백준] 1504 특정한 최단 경로  (0) 2022.07.30
[백준] 6087 레이저 통신  (0) 2022.07.17
[백준] 15961 회전 초밥  (0) 2022.07.16
[백준] 10217 KCM Travel  (0) 2022.07.15

댓글