백준 11780 플로이드 2 파이썬 풀이

난이도 : 골드2

풀이일 : 2402117

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

11780번: 플로이드 2

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys, heapq

def minicost(num):
    visited = [int(1e9)] * (n + 1)
    visited[num] = 0
    queue = []
    heapq.heappush(queue, [0, num, [num]]) # 비용, 다음 목적지, 거쳐간 도시

    # 각 도착지까지의 최소 비용으로 거쳐간 도시 저장
    temp = [[] for _ in range(n + 1)]

    while queue:
        cost, x, past = heapq.heappop(queue)
        if cost <= visited[x]:
            for add, nx in load[x]:
                # 최소 비용 경로 발견 시, temp 재할당
                if visited[nx] > cost + add:
                    visited[nx] = cost + add
                    temp[nx] = past + [nx]
                    heapq.heappush(queue, [cost + add, nx, past + [nx]])
    # result 배열에 최종 temp 반영
    result.append(temp)

    # 각 도착지까지의 최소 비용 출력
    for i in range(n):
        print(visited[i + 1] if visited[i + 1] < int(1e9) else 0, end=" ")

    return print()


n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
load = [[] for _ in range(n + 1)]
result = []

# 정보 입력
for _ in range(m):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    load[a].append([c, b])

# 각 출발지에서 모든 도착지로 최소 비용 경로 탐색
for i in range(n):
    minicost(i + 1)

# 각 출발지에서 최소 비용 거리로 이동 시 경로 출력
for i in range(n):
    for j in range(1, len(result[i])):
        # 경로의 길이
        print(len(result[i][j]), end=" ")
        # 거쳐간 도시
        for k in result[i][j]:
            print(k, end=" ")
        print()

• 이전 게시글에서 풀었던 플로이드 문제에서 각 최소비용 이동 경로를 출력하기 위해 result, temp 배열 추가
• heapq의 두 번째 인자 리스트에 이제까지 지나온 경로 리스트를 추가
• 3중 반복문
  • 0번째 요소를 제외하기 위해 j 조건을 1 ~ len(result[i])로 설정
  • 거쳐간 도시의 수 출력
  • 거쳐간 도시 번호 출력

---

느낀점

• 처음에는 visited 배열을 2차원으로 만들었었는데, 나중에 접근하기가 어려울 것 같아 꼭 필요한 경우가 아니라면 분리하는 게 좋다는 친구의 조언이 떠올라서 result, temp를 만들었다.
• 삼중 반복문에서 j의 조건도 for j in result[i] 로 적었다가 0번째 요소들을 빼기위해 바꿨더니 아주 지저분하고 읽기 힘든 코드가 되어버렸다.
• 썩 잘 푼 코드는 아닌 것 같지만 일단 티어 높은거 한 문제 풀어서 기분이 좋다