[코테] 백준 20188번 : 등산마니아 (java)

❓문제

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

20188번: 등산 마니아

 

---

🔅해석

참고 영상

https://www.youtube.com/watch?v=YkDv-O4dxfM&t=475s&ab_channel=%EC%9D%B4%EC%83%98%EC%BD%94%EB%94%A9

 

 

핵심

모든 구간에 대한 경우의 수는 조건에 맞는 모든 간선을 지나는 횟수의 총합이다.

 

 

 

 

이 문제는 노드 1(정상)을 제외한 노드 i와 노드 j를 방문할 때 최소 경로의 수로 경우의 수를 구한다.

각 간선의 방문 누적 횟수의 총합이 문제의 정답이 된다.

 

List, DFS 프로그래밍 개념과 경우의 수 구하는 Combination 개념을 알아야한다.

 

용어

노드 : 오두막

간선 : 오솔길

루트 노드 : 트리의 최상위에 위치하는 노드

리프 노드 : 가장 끝단에 위치한 노드로서 자식이 없는 노드

 

1. 트리 생성

List<Integer>[] tree = new List[n+1];
int subTree[] = new int[n+1];

노드끼리 연결된 전체적인 트리를 담는 List 객체의 tree와 노드 n개를 순회하면서 n번째노드를 루트노드로 하는 서브트리에 포함되는 노드의 수를 구하는 subTree를 만든다.

인덱스는 0부터 시작인데, 노드번호는 1번부터 시작하므로 방 크기를 하나 크게 잡는다.

 

2. 인접리스트로 tree 표현

		for (int i=0; i<n-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			tree[start].add(end);
			tree[end].add(start);
		}

 

위 사진처럼 사용자 입력에 따라 연결된 트리를 만든다.

 

3. dfs(깊이 우선 탐색)을 통해 subTree 값 채우기

각 노드를 기준으로 본인을 루트노드로 하는 서브트리(subTree)에 포함되는 노드의 수를 구한다.
예를들어, subTree[6]은 자신(6번), 2번, 8번 노드로 이루어져 3개의 노드의 수를 갖는다.

	private static int dfs(int index) {	
		
		for(Integer node : tree[index]) {
			
			if(visited[node]) {
				continue;
			}
			visited[node] = true;
			subTree[index] += dfs(node);
		}
		return subTree[index];
		
	}

 

 

4. 간선의 경우의 수 구하기

		for (int i=2; i<=n; i++) {
			int restNodeCnt = n - subTree[i];
			variety += nC2(n) - nC2(restNodeCnt);
		}
		System.out.println(variety);

	//콤비네이션(조합, 경우의수) 공식
	private static long nC2(int n) {
		return (long) n * (n-1) / 2;
	}

 

nC2 : 트리에서 노드 i와 노드 j를 방문할 때 이용하는 간선의 수를 구한다.

 

2번 노드 위로 뻗어 나가는(부모로 가는) 간선 부터 마지막 노드 위로 뻗어 나가는 간선까지 순회하면 모든 간선을 고려하게 된다.

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
//등산 마니아
	static List<Integer>[] tree;
	static int subTree[];	
	static boolean visited[];
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		tree = new List[n+1];	//인덱스는 0부터 시작인데, 노드번호는 1번부터 시작하기에 방 크기를 하나 크게 잡는다.
		for (int i=0; i<=n; i++) {
			tree[i] = new ArrayList<>();
		}
		
		for (int i=0; i<n-1; i++) {	//인접리스트를 트리로 표현
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			tree[start].add(end);
			tree[end].add(start);
		}
		
		subTree = new int[n+1];		//i번째 노드를 루트노드로 하는 서브트리에 포함되는 노드의 수
		for (int i=1; i<=n; i++	 ) {
			subTree[i] = 1;
		}
		
		visited = new boolean[n+1];
		visited[1] = true;		//루트노드부터 시작
		dfs(1);
		
		long variety = 0;
		
		//2번 노드 위로 뻗어 나가는(부모로 가는) 간선 부터 마지막 노드 위로 뻗어 나가는 간선까지 순회하면 모든 간선을 고려하게 된다.
		for (int i=2; i<=n; i++) {
			int restNodeCnt = n - subTree[i];
			
			variety += nC2(n) - nC2(restNodeCnt);
		}
		System.out.println(variety);
	}
	
	//콤비네이션(조합, 경우의수) 공식
	//n^2이 int를 초과하므로 long으로 선언
	private static long nC2(int n) {
		return (long) n * (n-1) / 2;
	}
	
	//각 노드를 기준으로 본인을 루트노드로 하는 서브트리에 포함되는 노드의 수를 구한다.
	//예를들어, subTree[1]은 자신(1번), 2번, 3번 노드로 이루어져 3개의 노드의 수를 갖는다.
	private static int dfs(int index) {	//깊이 우선 탐색을 통해 루트노드부터 리프노드까지 내려가며 subTree 값을 채운다.
		
		for(Integer node : tree[index]) {
			
			if(visited[node]) {
				continue;
			}
			visited[node] = true;
			subTree[index] += dfs(node);
		}
		return subTree[index];
	}
}

 

---

❗결과