백준 1185 유럽여행

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

1185번: 유럽여행

위 문제는 다양한 경우의 수가 있을 것 같지만, 문제에 걸린 제한을 통해 '자동'으로 코너 케이스가 다 사라졌다고 생각한다. 증명할 수만 있으면 자신 있게 코드를 제출할 수 있다.

 

가장 중요한 조건은 N-1개의 길만 남겨야한다는 것이다. 이를 통해 모든 정점들이 빠짐없이 연결되는 트리구조를 갖게 된다는 것을 알 수 있다. 사이클이 없다는 것이다. 여기서 최소 스패닝 트리를 활용해볼 수 있지 않을까 하는 생각이 든다.

또 다른 조건은 시작한 도시에서 여행을 마쳐야 한다는 것이다. 이를 통해 모든 경로를 꼭 2번씩 지난다는 것을 알 수 있다. 이 부분이 중요하다. 

왼쪽 그림은 문제의 예시이다. 이 중에서 N-1 개의 경로, 즉 4개의 경로만 남겨야 한다. 단순히 가중치가 낮은 경로만 선택하면 될 것 같지만, 이 문제에서는 각 도시에서 '숙박비'도 내야 한다. 이 때문이 혼란이 생겨난다. 가중치가 매우 낮아도 숙박비가 비싼 도시를 너무 자주 방문해야 한다면 전체 비용이 커질 수 있는 것이다.

그렇다면 경로의 가중치와 양끝 도시의 숙박비들을 모두 합한 값으로 정렬하면 어떨까? 뭔가 괜찮은 것 같지만 조금 찝찝하다. 경로 가중치+양끝 도시의 숙박비들 합이 더 크지만, 이용 횟수가 적어서 전체 비용이 적어지는 케이스는 없을까라는 생각을 하게된다.

이를 해결하기 위해 다음 그림을 보자.

 

 

 

 

 

 

왼쪽의 그림은 N-1개의 경로만 남겨서 트리구조를 만든 상태이다. 이제 시작점을 정해주면 된다. 1~5까지 선택지가 있다. 아무데서나 시작해서 비용을 정리해본다면, 중요한 사실을 깨달을 수 있다. 모든 경로를 2번씩 반복한다는 점이다. 어디에서 시작해도 마찬가지다.

 

이를 조금 더 쉽게 이해하기 위해 다른 형태의 트리 구조를 보자

 

 

 

 

 

 

 

왼쪽의 그림은 바로 윗 그림을 2가 루트가 되도록 재배치한 것이다. 1, 3, 4가 2의 자식 노드, 5가 4의 자식 노드인 형태가 된다. 트리의 중요한 점은 자식 노드 관점에서 봤을 때, 부모 노드로 가는 길은 단 한 개라는 것이다. 루트가 2라는 것은 2가 시작 도시이고, 유럽 여행을 마치려면 모든 길을 2번씩 지나가게 되는 것이다. 이를 통해 위에서 의심되었던 각 경로의 이용 횟수는 모두 동일하다는 점을 알 수 있다. 또한 모든 도시를 방문해야 하기 때문에 숙박비가 높다고 스킵하는 경우가 없다. 이는 결국 숙박비+경로 가중치로 정렬할 수 있다는 것을 말한다.

 

또한, 왼쪽 그림에서 각 도시의 숙박비를 몇 번씩 내야 하는지도 알 수 있다. 

1, 3, 5번 도시는 한 번만 방문, 2번 도시는 3번, 4번 도시는 2번 방문한다. 이는 각 정점과 연결된 경로 개수로 바로 파악 가능하다. 여기에 시작 도시 방문비만 한번 더 추가로 더해주면 된다.

 

이제 모두 파악되었다. 트리구조가 완성되면, 각 경로 가중치 합 * 2 + 각 도시별 방문비 총액 + 시작도시 숙박비가 전체 비용이 된다.

어느 도시에서 출발해도 시작도시 숙박비를 제외한 부분은 고정이다. 가장 숙박비가 저렴한 도시를 선택하면 된다.

 

최소 스패닝 트리 알고리즘을 사용할 경우, 경로 정보 배열을 정렬할 때 각 원소로 각 경로 가중치 합 * 2 + 각 도시별 방문비 총액 를 넣어주면 된다. (각 정점별로 몇 개의 경로가 연결되는지를 따져볼 필요 없다. 여기까지 꼭 해야 할 필요는 없지만)

 

<알고리즘>

최소 스패닝 트리

 

<코드>

const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')

const [n, p] = input[0].split(' ').map(e => Number(e))
const cost = [1001]
let min = 1001
for (let i = 0; i < n; ++i) {
    const v = Number(input[i + 1])
    cost.push(v)
    min = Math.min(min, v)
}

const paths = []
for (let i = 0; i < p; ++i) {
    const [s, e, w] = input[i + 1 + n].split(' ').map(e => Number(e))
    paths.push([s, e, 2 * w + cost[s] + cost[e]])
}

paths.sort((a, b) => a[2] - b[2])

const root = []
for (let i = 0; i < n + 1; ++i)root.push(i)
const find = a => {
    if (root[a] === a) return a
    root[a] = find(root[a])
    return root[a]
}
const merge = (a, b) => (root[root[a]] = root[b])

let t = min
for (const path of paths) {
    const [s, e, ws, w] = path
    if (find(s) === find(e)) continue
    merge(s, e)
    t += ws
}
console.log(t)