[백준OJ] 8012번 한동이는 영업사원!

www.acmicpc.net/problem/8012

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

---

 

-풀이-

트리를 선언하고 m개의 도시를 순서대로 움직일때 최소시간을 출력해야 한다.

a노드에서 b노드까지의 최소 거리를 구할 때 , 다익스트라를 사용해보았는데, 매번 다익스트라를 돌리기엔 시간초과가 났다.

그럼 어떻게 하면 좋을지 생각을 해보았는데, 어차피 최소한으로 움직이려면 a-> a와 b의 최소 공통조상->b 로 움직여야 최소거리가 된다.

그럼 한개의 간선의 이동시간이 1이므로, 한 노드의 깊이가 루트(1번노드) 에서 해당 노드까지 걸리는 시간이 된다.

 

문제속 입력을 예로 들면 노드들 아래 적혀있는 조그만한 숫자가 깊이가 된다.

3과 4의 깊이를 표현하자면

 

이런식으로 깊이가 설정이 된다.

우리가 여기서 3->4로 가는 최소 시간을 알고싶다면, 3->5->4 의 거리를 구해주면 되는데 우리가 알고있는것은

3->5->1의 시간과 4->5->1 의 시간이다. 따라서 두 깊이를 더해준 뒤, 필요없는 5의 깊이를 2배한값을 빼준다면, 3->4까지의 최소시간을 구할 수 있다.

 

정리하자면 x노드와 y노드 사이를 움직이는 최소시간을 구하려면 , depth[a]+depth[b]- 2 * depth[lca(a,b)] 를 해주면 된다.

 

여기서 조심해야할것은 m개의 줄에 입력된 순서대로 방문을 해야한다는 것이다. (문제 설명이 부족해서 이해하는데 좀 걸렸다)

 

-시간 복잡도-

초기 높이설정 dfs 는 O(N)

lca 알고리즘은 O(logN) 이 된다.

따라서 최종 시간 복잡도는 O(MlogN)이 된다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N = 30001;
int max_height = (int)floor(log2(MAX_N));
int n, m;
vector<vector<int>> v;
int depth[MAX_N];
int ancestor[MAX_N][30];

void dfs(int now, int parent, int d) {
	depth[now] = d;
	ancestor[now][0] = parent;

	for (int i = 1; i <= max_height; i++) {
		int prev = ancestor[now][i - 1];
		ancestor[now][i] = ancestor[prev][i - 1];
	}

	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (next != parent) {
			dfs(next, now, d + 1);
		}
	}
}

int lca(int a, int b) {
	if (depth[a] > depth[b]) {
		int temp = a;
		a = b;
		b = temp;
	}
	for (int i = max_height; i >= 0; i--) {
		if (depth[a] <= depth[ancestor[b][i]]) b = ancestor[b][i];
	}
	if (a == b) return a;
	for (int i = max_height; i >= 0; i--) {
		if (ancestor[a][i] != ancestor[b][i]) {
			a = ancestor[a][i];
			b = ancestor[b][i];
		}
	}
	return ancestor[a][0];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	v.resize(n + 1);

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0, 0);

	cin >> m;
	int now, prev;
	cin >> prev;
	int answer = 0;
	for (int i = 1; i < m; i++) {
		cin >> now;
		int LCA = lca(now, prev);
		//a->b까지 가는 경로의 최단거리= a의 깊이+b의 깊이 - 2*lca의 깊이
		//왜냐하면 a의 깊이+b의 깊이를 해주는 사이에 루트->lca까지 2번 겹치므로 빼주면된다
		answer += depth[now] + depth[prev] - 2 * depth[LCA];
		prev = now;
	}
	cout << answer;
}