취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17842번 문제인 버스 노선이다.
문제는 아래 링크를 확인하자.

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

먼저 도로망의 리프노드들에 대해 생각해보자.

모든 리프 노드를 지나는 버스 노선이 필요하므로, 총 리프 노드의 개수를 K라 하면 적어도 (K+1)/2개의 버스 노선이 필요할 것이라는 점을 알 수 있다.

이제 모든 경우 버스 노선을 (K+1)/2개만 만들어도 됨을 증명하자.

0. 현재의 트리의 리프 개수가 둘 이하이면 노선 설정을 어떻게 해야할지는 자명하다. 이 경우 알고리즘을 종료한다.

1. 트리에서 한쪽에 연결된 노드가 리프이면서 차수가 2인 노드가 없어질 때까지 리프노드를 제거한다. 이를 역추적하여 복구하는 일은 단순작업이다.

2. 모든 리프들이 하나의 노드에 연결되어있다면 이 그래프에서 버스 노선을 (K+1)/2개만 만들어도 됨은 자명하다. 이러한 경우 알고리즘을 종료한다.

3. 2가 아니므로, 트리에는 리프 노드가 연결된, (리프가 아닌) 서로 다른 두 노드 X, Y가 존재한다. 이 때, X에 연결된 리프와 Y에 연결된 리프를 연결하는 버스노선을 하나 결정하고, 각 리프를 그래프에서 지운다. X 노드에는 (1) X와 Y를 잇는 경로 위에 있는 노드와 (2) 선택한 리프노드 외에도 (3) 제 3의 노드가 적어도 하나 이상 연결되어있어야 한다. 현재 트리는 1번 과정에서 "한 쪽에 연결된 노드가 리프이면서 차수가 2인 노드가 없어질 때까지 리프노드를 제거"한 상태이기 때문이다. 따라서 X의 리프를 하나 제거하더라도 X는 차수가 2 이상이므로 X가 새로이 리프가 되는 일은 발생하지 않는다. 이 논리는 Y노드에도 마찬가지로 적용할 수 있다.

4. 0으로 돌아간다.

이 문제의 풀이는 차수가 2 이상인 노드 R을 잡아 R의 자식을 루트로 하는 두 서브트리를 생각해 각 서브트리에서 리프를 하나씩 지워나간다는 귀납적 증명이 알려져있는데, 글쓴이의 생각으로는 이는 엄밀하지 못한 증명으로 보인다. R의 차수가 3이고 R의 두 선택한 자식이 각각 리프였던 경우 두 리프를 지우면 R이 새로운 리프노드가 되어 트리의 리프 수가 둘 감소한 것이 아닌 하나만 감소하게 되기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int degree[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int cnt = 0;
	int N; cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		degree[x]++; degree[y]++;
	}

	for (int i = 0; i < N; i++) {
		if (degree[i] == 1) cnt++;
	}
	cout << (cnt + 1) / 2;
}