[Python] 1185번 유럽여행

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

1185번: 유럽여행

---

 

24/03/21

 

 

MST 응용 문제로, 아이디어를 사용해서 MST를 구하는 문제로 "변형"시켜야 해결할 수 있다.

---

 

문제 접근 방식:

 

 

먼저 문제를 보면 최소 비용이 되도록 길을 남길 것을 요구하고 있고, 길의 개수는 $N-1$개가 되도록 하라고 했으니, MST관련 문제임을 확인할 수 있다.

 

그러면 어떻게 접근해야 할까?

 

예제 입력 1을 예시로 들며 접근해 보자.

 

예제 입력 1의 그래프

 

위의 사진은 예제 입력 1의 그래프를 나타낸 모습이다.

 

각 도시의 번호를 도시 위아래에, 각 도시를 방문할 때 드는 비용은 도시 위에, 도시와 도시를 잇는 길의 비용은 길 위에 표현했다.

 

위의 그래프를 최소 비용으로 순회하면 다음과 같은 모양을 얻을 수 있다.

 

 

이 모습을 유의 깊게 보면, 어떤 도시에서 다른 도시로 갈 때 항상 그 사이의 간선을 두 번 지남을 알 수 있다.

 

따라서 어떤 간선의 가중치가 $w$라면, 그 가중치는 두 배로 계산해야 옳다.

 

또한, 우리는 MST의 형태로 바꾸어야 함을 목표로 하고 있기 때문에, 오로지 간선에만 가중치가 있도록 그래프를 바꾸고 싶다.

 

잘 관찰해 보면, 도시의 가중치는 그 도시로 가는 간선에 몰아줘도 무방하다.

 

예를 들어, $i$번 도시에서 $j$번 도시로 갈 때라고 상황을 설정한다면, $i$번 도시에 도착할 때 내야 하는 금액을 $i$번 도시를 떠난 후 바로 길 위에서 지불한다고 생각해도 무방하고, $j$번 도시에 도착할 때 내야하는 금액을 $j$번 도시에 도착하기 직전에 길 위에서 지불한다고 생각해도 무방하다.

 

따라서, 이를 종합적으로 생각해 보면, 다음과 같은 결론을 얻을 수 있다.

 

1. 모든 간선의 가중치를 두 배로 저장한다.
2. 이후 어떤 도시 $i$에 연결되어 있는 모든 간선마다 도시의 가중치 $w_i$를 더해준다.
3. 2번 과정을 모든 도시마다 진행해 준 뒤, MST를 구한다.

이 MST의 비용이 답이 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 1185번 유럽 여행
# MST
'''
접근 방법:
간선의 가중치를 두배 하고, 정점의 가중치를 간선에 몰아주자.
'''
import sys
input = sys.stdin.readline

N, P = map(int, input().split())
parent = list(range(N))
def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]
def union(node1, node2):
    p1 = find(node1)
    p2 = find(node2)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

city_weight = list(int(input()) for _ in range(N))
edges = []
for _ in range(P):
    S, E, L = map(int, input().split())
    S -= 1; E -= 1;
    W = 2*L+city_weight[S]+city_weight[E]
    edges.append((W, S, E))
edges.sort()
ans = min(city_weight)  # 시작 도시
MST_edges = 0
idx = 0
while MST_edges < N-1:
    W, S, E = edges[idx]
    idx += 1
    Ps, Pe = find(S), find(E)
    if Ps == Pe:
        continue
    else:
        ans += W
        MST_edges += 1
        union(S, E)
print(ans)

ezgif.com-animated-gif-maker.gif

0.29MB