[BOJ] 백준 3176번 도시 네트워크 (Java)

#3176 도시 네트워크

난이도 : 플레 4

유형 : 트리 / LCA / DP

3176번: 도로 네트워크

▸ 문제

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다.

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.

다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

▸ 출력

총 K개 줄에 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

 

문제 풀이  

LCA 풀이방식으로 두 노드의 부모노드를 구한 다음 세 노드의 정보를 이용해서 최소, 최대 거리를 찾게되면 O(NM)이라는 시간복잡도를 갖게 되어 시간초과가 발생할 것이다. 좀 더 효율적인 방법으로 LCA+DP를 활용하여 2^h 부모노드에 대한 데이터를 다루며 시간복잡도를 O(MlogN)까지 저장할 수 있다.

 

LCA+DP의 연산이 이뤄지는 과정에서 최소,최대 거리를 구하는 로직만 첨가해주면 해당 문제를 풀이할 수 있다.

 

설계 및 구현

먼저 해당 트리의 높이와 루트 노드를 구해야한다. (트리의 높이는 이진트리라고 가정하고 구하였는데 통과했다.)

// 루트노드 구하기 
int rIdx=0;
for(int i=1; i<n+1; i++) {
	if(!root[i]) {
		rIdx=i;
		break;
	}
}

// 트리 높이 구하기 (올림)log2(n) + 1
static int getTreeH() {
	return (int)Math.ceil(Math.log(n)/Math.log(2))+1; 
}

 

트리의 높이로 부모 노드의 정보를 담을 parent[][], minRoad[][], maxRoad[][]의 배열 크기를 할당해주고, 루트노드로 해당 트리를 순회하여 초기값을 할당해준다.

• parent[cur][h] : cur노드의 2^h번째 부모노드를 저장해준다.
• minRoad[cur][h] : cur노드의 2^h번째 부모노드까지 가장 짧은 도로 길이를 저장해준다.
• maxRoad[cur][h] : cur노드의 2^h번째 부모노드까지 가장 긴 도로 길이를 저장해준다.

static void init(int cur, int h, int pa) {
	depth[cur] = h;
	for(City nxt : list[cur]) {
		if(nxt.to != pa) {
			init(nxt.to, h+1,cur);
			minRoad[nxt.to][0] =nxt.dis;
			maxRoad[nxt.to][0] =nxt.dis;
			parent[nxt.to][0] =cur;
		}
	}
}

 

초기값의 정보를 가지고 나머지 정보들을 입력해준다. (2^1, 2^2, ... , 2^h-1 번째 부모노드)

static void fillParents() {
	for(int i=1; i<h; i++) {
		for(int j=1; j<n+1; j++) {
			// j의 2^i 번째 부모노드 =  (j의 2^i-1번째 부모노드)의 2^i-1번째 부모노드
			parent[j][i] = parent[parent[j][i-1]][i-1];
			
			maxRoad[j][i] = Math.max(maxRoad[j][i-1], maxRoad[parent[j][i-1]][i-1]);
			minRoad[j][i] = Math.min(minRoad[j][i-1], minRoad[parent[j][i-1]][i-1]);
		}
	}
}

 

LCA 연산을 통해 최소, 최대 거리 구하기

1. a와 b노드가 주어지면 높이 순으로 정렬한다.
2. parent[][] 데이터를 활용하여 a,b의 높이를 맞춰준다.
   1. 해당 탐색 노드들의 최소, 최대 거리(min, max)를 구한다.
   2.  높이를 맞췄는데 a==b이면, LCA가 일치하므로 탐색을 종료한다.
3. 높이를 맞췄으면 최대 루트노드까지 탐색하며 LCA를 구해준다.
   1. 각 a,b노드들의 2^i부모노드가 갖고있는 최소, 최대 거리와 비교하며 min, max 값을 구한다.
4. 탐색이 완료되었으면 최종으로 min, max의 값을 반환한다.

 

시뮬레이션

최대 높이 3을 가진 트리의 구조를 지닌 예제를 통해 시뮬레이션을 돌려보자. 

트리 예제

parent[cur][i]

cur노드의 2^i번째 노드를 저장한다. 예를들어 7번 노드의 2^1번째 부모노드는 1번 노드이다.

2^0번째 부모노드	0	1	2	3	1	5	2	1	5
2^1번째 부모노드	0	0	1	2	0	1	1	0	1

 

minRoad[cur][i]

cur노드의 2^i번째 노드까지의 최소 도로 거리를 저장한다. 예를들어 4번노드의 2번째 부모노드(2번노드)까지의 최소 도로거리는 1이다.

2^0번째 부모노드	0	2	1	5	3	1	4	3	2
2^1번째 부모노드	0	0	1	1	0	1	2	0	2
2^2번째 부모노드	0	0	0	0	0	0	0	0	0

 

maxRoad[cur][i]

cur노드의 2^i번째 노드까지의 최대 도로 거리를 저장한다. 예를들어 6번노드의 2번째 부모노드(1번노드)까지의 최대 도로거리는 3이다.

2^0번째 부모노드	0	2	1	5	3	1	4	3	2
2^1번째 부모노드	0	2	2	5	3	3	4	3	3

 

이와 같은 데이터가 init()메서드와 fillParents()메서드를 통해 채워지게 된다. 그 다음 문제에서 두 노드 a,b가 주어지면 해당 데이터를 통해서 최소, 최대 거리를 구하면 된다.

 

7, 8번 노드를 연결하는 최소, 최대 도로 거리 구하기

위에서 설계한 LCA 연산을 통해 쉽게 구할 수 있다. LCA를 구하게 되면 7,8번의 최소 공통 조상은 1번 노드가 된다. LCA를 구하는 과정에서 2^0, 2^1, ... 노드들을 거치게되는데 그때마다 최소, 최대 도로 거리를 갱신해주면 된다.

 

1. 7번노드의 높이가 2이고 8번노드의 높이가 1이기 때문에 7번노드의 높이를 1로 맞춰준다.
   1. 7번노드의 2^0번째 부모노드와 8번노드의 높이가 일치한다. a = parent[7][0] = 2;
   2. 최소, 최대 거리 갱신
      1. minRoad[7][0]=4
      2. maxRoad[7][0]=4
2. 높이가 1로 같은 2번노드와 8번노드의 LCA를 구해준다.
   1. 2^0번째 부모노드에서 LCA를 구할 수 있다.
   2. a = parent[2][0] = 1
   3. b = parent[8][0] = 1
   4. 최소, 최대 거리 갱신
      1. minRoad = (minRoad, (minRoad[2][0],minRoad[8][0])) = (4,(2,3)) = 2;
      2. maxRoad = (maxRoad, (maxRoad[2][0],maxRoad[8][0])) = (4,(2,3)) = 4;

 

따라서 7,8번 노드를 연결하는 경로에서 가장 짧은 도로의 길이는 2, 가장 긴 도로의 길이는 4임을 알 수 있다.

 

7,8번 노드의 최소 거리는 2, 최대 거리는 4이다.

 

풀이 코드 

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

public class Main {

	static class City{
		int to;
		int dis;
		
		public City(int to, int dis) {
			this.to = to;
			this.dis = dis;
		}
	}
	static int n,h;
	static List<City>[] list;
	static int[][] parent, minRoad, maxRoad;
	static int[] depth;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		depth = new int[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		h = getTreeH();
		
		parent = new int[n+1][h];
		minRoad = new int[n+1][h];
		maxRoad = new int[n+1][h];
		
		boolean[] root = new boolean[n+1];
		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());
			int c = Integer.parseInt(st.nextToken());
			list[a].add(new City(b,c));
			list[b].add(new City(a,c));
			root[b] = true;
		}
		
		int rIdx=0;
		for(int i=1; i<n+1; i++) {
			if(!root[i]) {
				rIdx=i;
				break;
			}
		}
		
		init(rIdx,1,0);
		fillParents();
		
		StringBuilder sb = new StringBuilder();
		int k = Integer.parseInt(br.readLine());
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			int[] res= LCA(d,e);
			sb.append(res[0]+" "+res[1]);
			if(i!=k-1) sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	
	static int getTreeH() {
		return (int)Math.ceil(Math.log(n)/Math.log(2))+1; 
	}
	
	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];
				
				maxRoad[j][i] = Math.max(maxRoad[j][i-1], maxRoad[parent[j][i-1]][i-1]);
				minRoad[j][i] = Math.min(minRoad[j][i-1], minRoad[parent[j][i-1]][i-1]);
			}
		}
	}
	
	static void init(int cur, int h, int pa) {
		depth[cur] = h;
		for(City nxt : list[cur]) {
			if(nxt.to != pa) {
				init(nxt.to, h+1,cur);
				minRoad[nxt.to][0] =nxt.dis;
				maxRoad[nxt.to][0] =nxt.dis;
				parent[nxt.to][0] =cur;
			}
		}
	}
	
	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;
		}
		
		int min = 1_000_001;
		int max = -1;
		for(int i=h-1; i>=0; i--) {
			if(Math.pow(2, i) <= depth[a] - depth[b]) {
				min = Math.min(min, minRoad[a][i]);
				max = Math.max(max, maxRoad[a][i]);
				a = parent[a][i];
			}
		}
		
		if(a==b) return new int[] {min,max};
		
		for(int i=h-1; i>=0; i--) {
			if(parent[a][i] != parent[b][i]) {
				min = Math.min(min, Math.min(minRoad[a][i], minRoad[b][i]));
				max = Math.max(max, Math.max(maxRoad[a][i], maxRoad[b][i]));
				a = parent[a][i];
				b = parent[b][i];
			}
		}
		
		min = Math.min(min, Math.min(minRoad[a][0], minRoad[b][0]));
		max = Math.max(max, Math.max(maxRoad[a][0], maxRoad[b][0]));
		return new int[] {min,max};
	}
}