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

 

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

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

www.acmicpc.net

두 정점간의 거리는 ( 각 노드에서 노드가 길이가 1일경우 )

int distance = depth[node1] + depth[node2] - 2 * depth[lca(node1, node2)];

가 되는데 코드 그대로 해석하자면 

root ~ node1 까지의 거리

+

root ~ node2 까지의 거리

-

2 * (root ~ (node1과 node2의 LCA) 까지의 거리 )

가 된다.

 

이문제에서 헷갈렸던 점은 한동이는 root에서 첫번째 방문도시로 순간이동 한다고 가정하고 풀어야 한다..

( 문제에 설명이 부족하다고 생각한다 )

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
#define MAX_N 30001
#define SWAP(a,b) {int t = b; b = a; a = t;}
vector<int> vec[MAX_N];
bool visit[MAX_N];
int depth[MAX_N];
int par[MAX_N][20];
int dis[MAX_N];
vector<int> m_vec;
void dfs(int now, int nowDepth, int prev) {
     visit[now] = true;
     depth[now] = nowDepth;
     par[now][0] = prev;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], nowDepth + 1, now);
          }
     }
}
 
 
int lca(int x, int y) {
     int ret = 0;
     if (depth[x] > depth[y]) SWAP(x, y);
 
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}
 
int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N;
     for (int i = 0; i < N - 1; i++) {
          int a, b;
          cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dfs(1, 0, 1);
     for (int j = 1; j <= 19; j++) {
          for (int i = 1; i <= N; i++) {
               par[i][j] = par[par[i][j - 1]][j - 1];
          }
     }
     cin >> M;
     int prev, now;
     long long ret = 0;
     for (int i = 0; i < M; i++) {
          cin >> now;
          if (i)  ret += depth[prev] + depth[now] - 2 * depth[lca(now, prev)];
          prev = now;
     }
     cout << ret << "\n";
     
}
저작자표시 (새창열림)

'알고리즘 > [C++]BOJ' 카테고리의 다른 글

[백준BOJ] 13511_트리와 쿼리2 (C++)  (0) 2019.10.02
[백준BOJ] 11437_LCA (C++)  (0) 2019.10.02
[백준] 2269_수들의합 (C++)  (0) 2019.10.01

+ Recent posts

티스토리툴바