1833 고속도로 설계하기 (백준, python3)

 

시간 제한	메모리 제한
2초	128MB

문제

N(1≤N≤200)개의 도시로 이루어진 나라가 있다. 이 도시들 사이를 다니는 고속철도망을 만들어 도시 간의 이동을 편하게 하려고 한다. 단, 고속철도망을 만든 후에 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다.

시범 사업으로 몇 개의 도시 사이에 고속철도가 설치되었는데 그 결과가 매우 좋아 국가에서는 이 사업을 완성하기로 하였다. 이제 당신은 몇 개의 도시 사이에 고속철도를 추가로 설치하여, 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다.

그러나 이 사업은 워낙 돈이 많이 드는 사업이기 때문에, 이 사업에 드는 총 비용을 최소화 하려고 한다. 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어졌을 때, 총 비용을 최소로 하여 사업을 완성하여 보자.

예를 들어 아래와 같은 경우를 보자.

현재 1번 도시와 2번 도시, 2번 도시와 4번 도시, 1번 도시와 4번 도시 사이에 고속철도가 설치되어 있다. 각각의 수는 두 도시 사이에 고속철도를 설치하는데 드는 비용을 나타낸다. 예를 들어 2번 도시와 3번 도시 사이에 고속철도를 설치하면 10만큼의 비용이 든다는 것을 의미한다. 위의 그림에 나타나지 않은 비용은 다 1,000이라고 하자.

위와 같은 경우에는 2, 3번 도시 사이에 고속철도를 설치하고, 3, 5번 도시 사이에 고속철도를 설치하면, 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 갈 수 있으며, 이 경우는 10+20+30+10+10=80만큼의 총 비용으로 사업을 완성할 수 있다. 10+20+30은 이미 설치된 고속도로에 대한 비용을 의미한다.

2, 4번 도시를 연결하는 고속철도가 없더라도 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있지만, 이미 설치되어 있는 고속철도를 돈을 들여가며 파괴할 필요가 없으므로, 이런 건 생각하지 않기로 한다.

 

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음수라면, 그 두 도시 사이에 이미 고속철도가 설치되어 있는 경우를 의미한다.

 

출력

첫째 줄에 두 정수 C, M를 출력한다. C는 고속철도망을 설치하는데 든 총 비용이며, M은 새로이 설치한 고속철도의 개수이다. 다음 M개의 줄에는 새로 고속철도가 설치된 두 도시번호를 출력한다. 우리가 최소화 하려는 것은 C이다.

 

---

풀이

우선 알아야 할 개념: MST(최소신장트리)

 

이미 고속도로가 건설된 곳은 가중치를 0으로 두고 모든 도시에 대해 최소 신장 트리를 구성하면 최소 비용을 얻을 수 있다. 이미 깔린 노선을 무시하고 새로 지으면 최소 비용이 나오지 않나? 라는 질문을 할 수 있지만 크루스칼 알고리즘을 수행하면 가중치가 0인 간선을 우선 추가하게 되는데 이때 불필요한 경우를 제외한 모든 기존 노선을 다 이어놓고 시작하므로 상관이 없다.

 

최소 신장 트리가 구성되면 새로 깔아야 하는 고속도로 비용을 모두 더하고, 이미 지어져있는 고속도로의 비용까지 더해주면 끝.

 

정답 코드

import sys
input = sys.stdin.readline

def find(parent, k):
    while parent[k] != k:
        k = parent[k]
    return k

def union(parent, a, b):
    A = find(parent, a)
    B = find(parent, b)
    parent[a] = A
    parent[b] = B
    link = 0
    if A != B:
        parent[B] = a
        link = 1
    return parent, link

def solution():
    N = int(input())
    cost = [list(map(int, input().split())) for _ in range(N)]
    rail = []
    C, M = 0, 0
    install = []
    for i in range(1, N):
        for j in range(i):
            rail.append((cost[i][j], i, j))
            if cost[i][j] < 0: C -= cost[i][j]
    rail.sort()
    parent = [i for i in range(N)]
    for c, i, j in rail:
        parent, link = union(parent, i, j)
        if link and c >= 0:
            C += c
            M += 1
            install.append((i + 1, j + 1))
    print(C, M)
    for m in install:
        print(*m)

solution()