백준 32408: 대전 도시철도 2호선

문제 요약

대전시는 $N$개의 교차로와
$N-1$개의 도로가 교차로를 정점, 도로를 간선으로 하는 트리 구조를 이루고 있다. 교차로는 $1$번부터 $N$번까지 번호가 매겨져 있다. 대전시는 $1$번 교차로와 $N$번 교차로를 잇는 경로를 따라 대전 도시철도 1호선을 운행하고 있다. 이 경로에 포함되는 교차로와 도로에는 각각 역과 철도가 설치되어 있다.

대전시는 도시철도 2호선을 추가로 운행하려고 한다. 1호선과 비슷하게 2호선도 $S$번 교차로와 $E$번 교차로를 잇는 경로를 따라 역과 철도를 설치하려고 한다. $S$번과 $E$번 교차로는 1호선 역이 설치되지 않은 서로 다른 교차로여야 하고, 이용객이 1호선으로 환승할 수 있도록 2호선은 1호선 역을 적어도 하나 포함해야 한다.

대전 도시철도 2호선을 운행하기 위해 조건을 만족하는 두 교차로를 고르는 경우의 수를 구해보자. 단, 두 교차로의 순서를 바꾼 것은 같은 경우로 본다.

문제 분류

• 수학
• 그래프 이론
• 그래프 탐색
• 트리
• 조합론
• DFS

문제 풀이

문제를 이해하기가 좀 어려웠지만, 1번 정점과 N번 정점을 최단거리로 잇는 정점들이 1호선 역이고, 어떤 정점에서 다른 정점으로 방문할 때, 이 1호선 정점을 하나이상 포함하는 경우를 세는 것이다.
결론적으로 말하면, 우선 1호선 정점들을 먼저 표시를 한다. 나는 fir[i]의 값이 true인 경우 i번째 정점이 1호선인 것으로 파악했다.

이후, 현재 탐색중인 노드가 1호선이라면, 자신의 서로다른 자식 노드끼리 하나씩 골라 두개를 뽑는 경우의 수를 세어 누적시킨다. 마지막으로 자신 노드의 자식의 수를 반환하여 부모 노드에 전달한다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {
	static boolean visited[], fir[];
	static List<Integer> e[];
	static int n;
	static long res;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int u, v;
		n = Integer.parseInt(br.readLine());
		visited = new boolean[n];
		fir = new boolean[n];
		e = new List[n];
		for(int i = 0; i < n; i++)
			e[i] = new ArrayList<>();
		for(int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			e[u].add(v);
			e[v].add(u);
		}
		visited[0] = true;
		fir[0] = true;
		dfs(0);
		count(0);
		System.out.println(res);
	}
	static boolean dfs(int idx) {
		if(idx == n - 1) {
			fir[idx] = true;
			return true;
		}
		boolean ret = false;
		for(int it : e[idx]) {
			if(!visited[it]) {
				visited[it] = true;
				if(dfs(it)) {
					ret = true;
					fir[idx] = true;
				}
				visited[it] = false;
			}
		}
		return ret;
	}
	static long count(int idx) {
		long ret = 0, val = 0, temp;
		if(!fir[idx]) ret++;
		for(int it : e[idx]) {
			if(!visited[it]) {
				visited[it] = true;
				temp = count(it);
				ret += temp;
				visited[it] = false;
				if(fir[idx]) {
					res += val * temp;
					val += temp;
				}
			}
		}
		return ret;
	}
}