[BOJ] 백준 8012번 한동이는 영업사원! (Java)

#8012 한동이는 영업사원!

난이도 : 플레 4

유형 : 트리 / LCA / DP

8012번: 한동이는 영업사원!

▸ 문제

한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도시를 방문하는데 걸리는 최소의 시간을 알고싶어하는데, 한동이는 경영학과라 컴퓨터를 하지 못 하기 때문에 여러분이 한동이를 도와주자.

포항 시내의 도시들은 1부터 n까지 번호 지어져 있다. 한동이는 항상 포항시청에서 여행을 시작하고, 포항시청의 번호는 항상 1번이다. 모든 도시들은 양방향 도로로 연결되어있는데 한 도시에서 바로 길이 이어져있는 다른 도시로 이동하는데는 항상 1의 시간이 걸린다. 포항시청에서는 어떤 도시든지 갈 수 있다. 또한 포항의 도로는 굉장히 잘 되어있어서 도로끼리 사이클을 만들지 않는다.

여러분의 목표는 한동이가 모든 도시를 방문하는데 걸리는 최소의 시간을 출력하는 것이다.

▸ 입력

입력의 첫 줄에는 포항에 있는 도시의 숫자 n이 주어진다. 1 ≤ n ≤ 30,000.

다음 n-1줄에는 도시를 잇는 도로가 주어진다. 각 줄에는 정수 a와 b가 주어진다. 이는 a도시와 b도시를 잇는 도로가 존재한다는 의미이다. (1 ≤ a,b ≤ n; a≠b)

n+1번째 줄에는 정수 m이 주어지는데, 이는 한동이가 방문해야 할 도시의 숫자를 의미한다. 1 ≤ m ≤ 5,000 그 후 m개의 줄에는 한 줄에 하나씩 한동이가 방문해야 할 도시의 숫자가 순서대로 주어진다.

▸ 출력

첫 줄에 한동이가 방문해야 할 모든 도시를 방문 할 수 있는 최소 시간을 출력한다.

 

문제 풀이  

노드 사이의 거리를 빠르게 탐색하는 기법으로 LCA를 활용하는 방법이 있다. 트리의 두 정점이 있을 때 두 정점의 LCA(최소공통조상)을 찾아주면 간단한 연산으로 구할 수 있기 때문이다.

• 정점 a - 정점 b 사이의 거리 : dis[a] + dis[b] - 2*dis[lca]

5, 6번 정점의 LCA는 2번

💡 LCA에 대한 자세한 설명은 여기를 참고해주세요

 

설계

1. 양방향 트리 데이터를 입력받는다.
2. LCA를 구하기 위한 데이터를 초기화시켜준다.
   1. dis[cur]: 루트로부터 해당 정점(cur)사이의 거리
   2. depth[cur]: 해당 정점(cur)의 높이
   3. parent[cur][h]: 해당 정점(cur)의 2^h번째 부모
3. 주어진 도시들을 순서대로 방문해야 하므로 각 인접한 방문 도시들의 LCA를 구하여 거리를 구한다.
   1. totalCost += dis[a]+dis[b]-2*dis[lca];
4. 이렇게 구한 최소시간(totalCost)을 출력한다.

 

풀이 코드

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

public class Main {
	static int n, h;
	static List<Integer>[] list;
	static int[] depth, dis;
	static int[][] parent;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		StringTokenizer st;
		for(int i=0; i<n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		h = getTreeHeight();
		dis = new int[n+1];
		depth = new int[n+1];
		parent = new int[n+1][h];
		
		init(1,1,0);
		fillParents();
		
		int m = Integer.parseInt(br.readLine());
		int[] city = new int[m];
		for(int i=0; i<m; i++) {
			city[i] = Integer.parseInt(br.readLine());
			
		}
		
		int totalCost =0;
		for(int i=1; i<m; i++) {
			int a = city[i-1];
			int b = city[i];
			int lca = LCA(a,b);
			totalCost += dis[a]+dis[b]-2*dis[lca];
		}
		System.out.println(totalCost);
	}
	
	static int LCA(int a, int b) {
		int ah = depth[a];
		int bh = depth[b];
		
		if(ah < bh) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		
		for(int i=h-1; i>=0; i--) {
			if(Math.pow(2, i) <= depth[a] - depth[b]) {
				a = parent[a][i];
			}
		}
		
		if(a==b) return a;
		
		for(int i=h-1; i>=0; i--) {
			if(parent[a][i] != parent[b][i]) {
				a = parent[a][i];
				b = parent[b][i];
			}
		}
		return parent[a][0];
	}
	
	static int getTreeHeight() {
		return(int)Math.ceil(Math.log(n)/Math.log(2)) +1;
	}
	
	static void init(int cur, int h, int pa) {
		depth[cur] = h;
		for(int nxt : list[cur]) {
			if(nxt != pa) {
				dis[nxt] = dis[cur] +1;
				init(nxt, h+1, cur);
				parent[nxt][0] = cur; 
			}
		}
	}
	
	static void fillParents() {
		for(int i=1; i<h; i++) {
			for(int j=1; j<n+1; j++) {
				parent[j][i] = parent[parent[j][i-1]][i-1];
			}
		}
	}
}