[C++] 백준 28119번 - Traveling SCCC President

 

2025년 5월 16일

문제 링크 : 백준 28119번 - Traveling SCCC President

 

문제 접근

 

문제를 요약하면 다음과 같다.

 

요약

1. 대학 캠퍼스에는 1부터 N 까지 번호가 붙어 있는 N 개의 건물이 있다. 건물 번호는 중복 없이 1부터 N 까지 정수가 정확히 하나씩 존재한다.

2. 서로 다른 두 건물을 연결하고 1부터 M 까지 번호가 붙어 있는 M 개의 도로가 있다. 각 도로는 통행하는 데 일정 시간이 소요된다. 두 건물을 직접 잇는 도로가 존재하지 않더라도, 다른 이어진 건물로 우회하여 이동할 수 있다면 두 건물은 연결되어 있다고 표현한다. 모든 건물은 도로를 통해 이어져 있으며, M 은 최소 N - 1개 존재한다. 

3. 건물 N 개 모두를 주어진 차례대로 방문해야 한다.

4. 한 번 방문한 건물은 다시 방문할 때 순간 이동 장치를 사용할 수 있기에 다른 어느 건물에서 방문한 건물로 이동하는 시간이 소요되지 않는다.

5. 처음 방문할 건물을 시작으로 모든 건물을 방문한 후, 다시 처음 건물로 되돌아와야 한다.

 

 

문제에서 순간 이동 장치를 사용하면 지금까지 방문했던 건물 중 원하는 곳으로 순식간에 이동할 수 있다. 는 구문을 이해하면 해당 문제를 어떻게 풀어야 하는지 이해할 수 있다.

1번, 2번 4번 건물을 방문한 상태라고 가정.

대학 캠퍼스가 위와 같고, 현재 1번 ->2번 -> 4번 건물을 방문한 상태라고 가정해보자. (아직 3번 건물은 방문하지 않은 상태임)
그렇다면 4번 건물에서 2번 건물, 4번 건물에서 1번 건물 등등.. 이미 방문한 건물로 되돌아가는 데 소요되는 시간은 중간에 도로가 아무리 많아도 순식간에 이동할 수 있다는, 즉 0만큼 시간이 소요된다는 의미이다.

 

문제에서 주어진 해당 조건 때문에 사실상 모든 건물을 방문한 상태라면 다시 처음 방문했던 건물로 되돌아가야 한다는 요약 - 5번 내용은 의미가 없다는 것을 알 수 있다.

 

또한, 건물 N 개를 모두 방문하는데, 입력으로 방문 순서가 주어지며 해당 순서대로 건물을 방문해야 한다는 조건이 주어져있다.

이 또한 순간 이동이 가능하다는 조건 때문에 의미가 상쇄된다. 순간 이동 덕분에 이미 방문한 건물로 경유해서 다른 방문하지 않은 건물로 가는 시간 중, 이미 방문한 건물로 경유하는 데 소요하는 시간을 고려하지 않을 수 있다. 따라서 만약 모든 건물을 방문할 수 있는 여러가지 도로의 조합 중, 총 소요 시간이 짧은 도로의 조합을 찾는다면 해당 조합을 구성하는 도로의 총 소요 시간이 문제에서 원하는 해가 된다.

 

결국 다음과 같은 문제로 귀결된다.

모든 N 개의 건물을 연결하는 도로들의 총 소요 시간이 가장 짧은 도로 조합이 존재할 때,
해당 도로 조합의 총 길이를 구하시오.

이는 최소 신장 트리인 MST(Minimum Spanning Tree) 문제와 같다는 것을 알 수 있다.

 

이 외에도 도로의 개수 M 의 최소 개수가 건물의 개수 N - 1인 점  또한 MST 문제라는 데에 뒷받침이 가능한 근거가 된다.

---

입력 예제

 

4 6 1
1 2 1
2 3 2
3 4 3
1 4 4
2 4 5
1 3 2
1 2 3 4

 

 

1. 입력값에 대한 초기 상태.

 

나는 해당 MST 문제를 Prim's algorithm으로 해결할 것이다.

 

MST에 포함된 건물은 빨간색 원 표시로 체크할 것이고, 방문 건물 순서는 사실 의미 없지만 입력으로 들어왔으니 적어놓았다. (이후에도 쓸 일은 없는 정보다.)

pq는 Min-heap으로 구현된 우선순위 큐이며, 도로 통행 시간을 기준 더 작은 시간의 도로가 우선순위가 높도록 책정하였다. 그림 설명을 위해 Unsorted Array로 표현하였다. 또한 pq의 각 요소는 {도로 통행 시간, 목적지 건물} 이다.

 

2. 임의의 건물을 방문 시작 건물로 체크하며 MST에 편입. 나는 1번 건물부터 방문하였다.

 

1번 건물을 방문 시작 건물로 설정하여 Prim's algorithm을 수행할 것이다.

1번 건물과 이어진 도로들 중, MST에 소속되지 않은 건물로 향하는 도로 정보를 pq에 삽입한다.

 

 

3.

 

pq에서 우선순위가 가장 높은, 즉 소요 시간이 가장 적은 도로를 pop 하여 해당 정보를 확인해보자.

해당 도로로 이으려는 건물이 MST에 소속되어 있지 않으므로 해당 도로를 채택하고 이어진 2번 건물을 MST로 편입시킨다.

 

4.

 

2번 건물과 이어진 도로들 중, MST에 소속되지 않은 건물로 향하는 도로 정보를 pq에 삽입한다.

 

5.

이후 같은 과정을 반복한다.

 

6.

 

7.

 

우선순위가 가장 높은 도로를 뽑아서 확인해보니, 이미 MST에 소속된 3번 정점으로 향하는 도로이므로 해당 도로 정보는 무시한다.

따라서 pq에서 pop 한 이후 작업은 무시하고 바로 다음 로직을 수행한다.

 

8.

 

 

9.

 

모든 건물이 MST에 소속되었으므로 더 이상 pq의 도로 정보를 확인할 필요가 없다.

따라서 로직을 종료하고 MST를 구성하는 모든 도로의 소요 시간을 합한다.

이는 문제에서 요구하는 해와 일치한다.

 

출력 예제

 

6

 

---

전체 코드

 

// 28119

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl "\n"

using namespace std;

vector<vector<pair<int, int>>> graph;
vector<int> meeting;
vector<bool> isMST;
int isMSTcnt;

void Prim(int start) {
	// min-heap
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	int min_dis = 0;
	
	while (!pq.empty()) {
		auto now = pq.top();
		pq.pop();
		int now_v = now.second;
		if (isMST[now_v]) continue;
		isMST[now_v] = true;
		isMSTcnt--;
		min_dis += -now.first;
		if (isMSTcnt <= 0) {
			break;
		}
		for (auto n : graph[now_v]) {
			int next_v = n.first;
			if (isMST[next_v]) continue;
			int weight = n.second;
			pq.push({ -weight, next_v });
		}
	}
	cout << min_dis;
}

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	int N, M, S;
	cin >> N >> M >> S;
	graph.resize(N + 1);
	isMST.resize(N + 1, false);
	isMSTcnt = N;
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[v].push_back({ u, w });
		graph[u].push_back({ v, w });
	}
	
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		meeting.push_back(a);
	}
	Prim(S);
}

 

 

---

풀이 후기

 

문제의 성격을 이해하면 실제 요구하는 바를 캐치할 수 있는 문제였다.

더 나아가 이해가 완료되면 왜 일부 입력 정보가 필요 없는지까지 알아낼 수 있었다.