[BOJ/Python] 1833_고속철도 설계하기

문제 출처:https://www.acmicpc.net/problem/1833

1833번: 고속철도 설계하기

문제

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이다.

예제 입력 1

5
   0  -10 1000  -20 1000
 -10    0   10  -30 1000
1000   10    0   30   10
 -20  -30   30    0   20
1000 1000   10   20    0

예제 출력 1

80 2
2 3
3 5

---

풀이

 

문제를 요약해보자.

 

• 1번 도시부터 N번 도시까지 총 N개의 도시(노드)가 존재한다.
• 임의의 도시에서 다른 임의의 도시로 이동할 수 있도록 고속철도(간선)를 설치해야 한다.
• 인접행렬 형태로 두 도시 사이의 고속철도를 설치할 때의 비용이 주어진다.
• 이 비용이 음수라면 이미 설치되어 있는 고속철도이고, 양수라면 새로 설치할 때의 비용이다.
• (이미 설치되어 있는 고속 철도의 비용) + (새로 설치할 때의 고속 철도의 비용)의 최소비용을 구해야 한다.
• 또한 새로 설치할 때 어떤 도시와 어떤 도시가 연결되어 있는지 또한 출력한다.

 

코드는 다음과 같다.

 

import sys
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n = int(sys.stdin.readline())
 
parent = [i for i in range(n+1)]
edges = []
cost_list = []
total_cost = 0
for _ in range(n):
    cost_list.append(list(map(int,sys.stdin.readline().split())))
 
for i in range(n):
    for j in range(i+1,n):
        if cost_list[i][j]<0:
            total_cost+=(-cost_list[i][j])
            union_parent(parent,i+1,j+1)
        else:
            edges.append((cost_list[i][j],i+1,j+1))
 
edges.sort()
 
result = []
l = 0
for cost,u,v in edges:
    if find_parent(parent,u)!=find_parent(parent,v):
        union_parent(parent,u,v)
        total_cost+=cost
        l+=1
        result.append((u,v))
 
print(total_cost,l)
for res in result:
    print(*res)

 

• 인접행렬로 주어진 간선들의 비용을 살펴본다.
• 만약 값이 음수라면, 이미 설치되어 있으므로 total_cost에 해당 값을 양수로 바꾸어 더해준다.
• 또한, 이미 설치되어 있다면 연결되어 있다는 의미이므로 union_parent 함수를 이용하여 하나의 집합으로 합친다.
• 만약 값이 양수라면, 아직 설치되어 있지 않은 고속철도이므로 edges 리스트에 해당 간선의 비용과 두 도시의 정보를 넣어준다.
• edges 리스트를 철도의 설치비용을 기준으로 오름차순으로 정렬한 후 for문을 이용하여 하나씩 살펴본다.
• 최종적으로 고속철도망을 설치하는데 든 총비용과 새로 설치한 철도의 개수를 출력하고, 새로 설치된 두 도시들을 출력한다.