[BOJ] 24545 Y

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

24545번: Y

리쓴 투 마 와....아


SUAPC에서 푼 문제 중 기록해두고 싶은 문제다.
대회 때 내가 1인분을 하는 데 기여해줬다.

대회 중에 더 이상 문제가 안 풀려서 한참 진전이 없었을 때 팀원들과 셋이 의논하면서 솔루션을 도출해냈다.
이야기하다가 내가 문득 트리의 지름이 떠올렸고, 트리의 지름에 있는 노드들을 보면서 리프 노드까지의 개수가 최대인 걸 구하면 되지 않을까? 라고 했다.
근데 반례가 있을 거 같았는데, 다른 두 분이 아니라고 맞다고 하셨고, 그때 기령이가 수식을 적어가면서 증명해줬다.

5시간 중에 그때 막 텐션이 올랐던 참이라 이걸 정말 잘 짤 수 있을 것 같아서 내가 맡겠다고 했다.
다 짜고 나서 이전에 제출했던 코드에서 찾은 반례 등을 넣어보니 다 맞게 나왔고, 제출했더니 다행히 한 번에 맞았다.
대회에서 플레 문제를 한 번에 맞다니.
운도 좋았던 게, 며칠 전에 다른 팀이랑 연습하면서 두 번째 트리의 지름 문제를 한 번 봤던 상태였다.

int GetCnt(int cur, int before, const vector<vector<int>>& adj) {
	int ret = 0;
	for (const int& next : adj[cur]) {
		if (next == before) {
			continue;
		}
		ret = max(ret, GetCnt(next, cur, adj));
	}
	return ret + 1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<vector<int>> adj(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	queue<int> que;
	vector<bool> visited(n + 1, false);
	que.push(1);
	visited[1] = true;
	int last_node = 1;
	while (!que.empty()) {
		int cur = que.front();
		que.pop();

		last_node = cur;
		for (const int& now : adj[cur]) {
			if (visited[now]) {
				continue;
			}
			visited[now] = true;
			last_node = now;
			que.push(now);
		}
	}

	visited.clear();
	visited.resize(n + 1, false);
	int start_node = last_node;
	que.push(start_node);
	visited[start_node] = true;
	vector<int> before(n + 1, -1);
	while (!que.empty()) {
		int cur = que.front();
		que.pop();

		last_node = cur;
		for (const int& now : adj[cur]) {
			if (visited[now]) {
				continue;
			}
			visited[now] = true;
			before[now] = cur;
			que.push(now);
		}
	}

	vector<int> route;
	vector<bool> on_route(n + 1, false);
	for (int cur = last_node; cur != -1; cur = before[cur]) {
		route.push_back(cur);
		on_route[cur] = true;
	}

	if (route.size() == n) {
		cout << 0 << kEndl;
		return 0;
	}

	int max_cnt = 0;
	for (const int& cur : route) {
		for (const int& next : adj[cur]) {
			if (on_route[next]) {
				continue;
			}
			max_cnt = max(max_cnt, GetCnt(next, cur, adj));			
		}
	}

	cout << route.size() + max_cnt << kEndl;
}

처음에는 여기서 특정 노드가 트리의 지름에 속하는지 확인할 때 route 벡터에 저장된 걸 정렬해서 이분탐색 하려고 했다.
……
가끔 이럴 때가 있다. 눈앞에 닥친 것만 보다가 이상한 짓을 하는.
다행히 금방 정신 차리고 flag로 저장해두면 된다는 걸 깨달았다.

그리고 이 문제를 풀 때의 분위기가, 팀 대회의 재미가 충분히 발현되었던 거 같은 느낌.
셋이 이야기하면서 솔루션 도출하고, 한 이야기가 나왔을 때 그것에 대한 반례나 증명에서 다른 팀원이 서포트 하고, 그러다 확신이 들면 한 명이 코드를 작성하고 (이때도 다른 팀원의 도움을 받을 수도 있고), 제출하기 전에 셋이서 만들어놓은 예제를 넣어보면서 한 번 더 확인하고.

재밌었던 문제로 오래 기억될 거 같다.