[PS] 백준 #24520. Meet In The Middle

문제 정보

• 난이도: 플래티넘 IV
• 문제 주소: https://www.acmicpc.net/problem/24520
• 이 문제를 푼 이유: 알고리즘 스터디 - LCA

 

문제

신촌 왕국에는 $1$번부터 $N$번까지 $N$개의 마을이 있고 $N-1$개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다.

현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에 더 가깝다면 아주 불편해진다. 따라서 두 사람이 사는 각 마을까지의 거리가 정확히 같은 곳을 약속 장소로 정해야 할 것이다. 즉, Meet in the middle. 가운데에서 만나야 한다!

신촌 왕국 도로 정보와 만나려는 두 사람의 마을이 주어졌을 때, 약속 장소로 적절한 위치를 구해보자.

 

나의 풀이

처음에는 LCA를 쓰면 되겠지 하고 간단하게 풀릴 줄 알았는데, 의외로 안풀려서 시간을 많이 잡아먹었다. 우선 LCA를 구하고 최단경로의 길이를 구하는 과정은 앞의 문제 (1761번. https://pongkijoa.tistory.com/93) 와 동일하다. 그런데 최단 경로 사이의 중간 지점을 찾는 것은 쉽지 않았다. 하나하나 각 경로별로 증가시키면서 가기에는 매 쿼리마다 O(n)이 걸려서 시간 초과가 날 것이고.. 그 외에는 다른 아이디어가 잘 떠오르지 않았다. 결국 구글링을 통해 대회 해설지를 보고 힌트를 얻어서 풀었다.

이 문제는 "총 거리가 홀수이면 답이 존재하지 않고, 짝수이면 거리의 절반에 해당하는 정점을 희소 테이블을 이용하여 찾기" 가 핵심이였다. 이 과정이 아래 코드 LCA 찾기에서 5번에 해당하는데 goalNode를 알맞게 이동시키는 것이 꽤 어려웠다. 2^j층 위의 노드와 시작 노드의 거리차이를 구해서 총 거리의 절반보다 크면 스킵하고, 작으면 goalNode를 해당 노드로 옮긴다. 이 과정을 반복하면 O(log n)만에 정답 노드를 찾을 수 있다. 이 풀이를 떠올리지 못한 것은 LCA보다 희소 테이블에 대한 개념이 아직 익숙하지 않아서 그런 것 같았다.

#include <bits/stdc++.h>

using namespace std;

// 1, 2, 3, 4차 시도: 5% 틀렸습니다 - 99번째 줄 추가

#define SIZE 100000
#define MAX 17 // ceil(log2(100000));

int n, m;
int parent[SIZE + 1][MAX + 1];
int depth[SIZE + 1];
vector<vector<pair<int, long long>>> adj(SIZE + 1);
vector<long long> dist(SIZE + 1);

// dfs로 트리 제작하며 parent[i][0], depth 배열 채움 + dist 채움
void makeTreeByDFS(int curr, long long dis) {
    for (auto next : adj[curr]) {
        if (depth[next.first] == -1) {
            parent[next.first][0] = curr;
            depth[next.first] = depth[curr] + 1;
            dist[next.first] = dis + next.second;
            makeTreeByDFS(next.first, dis + next.second);
        }
    }
}

int main() {
    cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);

    // 정보 입력
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int u, v; long long w; cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back(make_pair(v, w)); // 0부터 시작
        adj[v].push_back(make_pair(u, w));
    }

    // 배열 초기화
    memset(parent, -1, sizeof(parent));
    fill(depth, depth + n, -1);
    depth[0] = 0; dist[0] = 0;
    makeTreeByDFS(0, 0);

    // parent 배열 채우기 (parent[i][j]: i번 노드의 2^j 층 위의 조상)
    for (int j = 0; j < MAX; j++) {
        for (int i = 1; i < n; i++) {
            if (parent[i][j] != -1) parent[i][j + 1] = parent[parent[i][j]][j]; 
        }
    }

    // Finding LCA
    while (m--) {
        int u, v; cin >> u >> v;
        u--; v--;
        int way[3]{}; // 경로

        // 1. 항상 depth[u] >= depth[v]
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        way[0] = u; way[2] = v; // u가 항상 깊은쪽

        // 2. u와 v가 같은 높이가 되도록 이동
        int j = 0;
        while (diff > 0) {
            if (diff % 2) u = parent[u][j];
            diff /= 2; j++;
        }

        // 3. u와 v가 다르면 2^j 높이 위로 이동 / 같으면 LCA 찾음
        if (u != v) {
            // 높이 2^17, 2^16, ..., 2^2, 2, 1 순으로 시도
            for (int j = MAX - 1; j >= 0; j--) {
                if (parent[u][j] != -1 && parent[u][j] != parent[v][j]) {
                    u = parent[u][j];
                    v = parent[v][j];
                }
            }
            // 두 정점 u, v의 부모가 같으므로 한 번 더 올림
            u = parent[u][0];
        }
        way[1] = u;

        // 4. way 에 따라서 nodeDist 값 구하기 (way[1]: LCA)
        long long nodeDist = dist[way[0]] + dist[way[2]] - 2 * dist[way[1]];
       // cout << "LCA 경로: " << way[0] << " -> " << way[1] << " -> " << way[2] << endl;
       // cout << "NODEDIST: " << nodeDist << endl;

        // 5. 거리의 절반에 해당하는 가중치가 어딨는지 찾기
        if (nodeDist % 2 == 1) { // 거리가 홀수면 끝
            cout << -1 << "\n"; continue;
        }
        else if (nodeDist == 0) { // 거리가 0이면 자기자신 출력
            cout << way[0] + 1 << "\n"; continue;
        }
        
        // 거리가 짝수면 절반 지점이 있는지 찾기
        // 일반성을 잃지 않게 루트에서 멀리 있는 쪽에서부터 계산
        int startNode = ((dist[way[0]] > dist[way[2]]) ? way[0] : way[2]);
        int goalNode = startNode;
        for (int j = MAX - 1; j >= 0; j--) {
            // if (parent[goalNode][j] != -1) cout << "2^" << j << "층 위 (" << parent[goalNode][j] + 1 << ")까지의 거리: " << dist[startNode] - dist[parent[goalNode][j]] << endl;
             if (parent[goalNode][j] != -1) {
                if (dist[startNode] - dist[parent[goalNode][j]] < nodeDist / 2) goalNode = parent[goalNode][j];
                if (dist[startNode] - dist[parent[goalNode][j]] == nodeDist / 2) { goalNode = parent[goalNode][j]; break; }
             }
        }
        if (dist[startNode] - dist[goalNode] != nodeDist / 2) cout << -1 << "\n";
        else cout << goalNode + 1<< "\n";
    }
}

/*
10 200
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000

13 100
1 2 3
2 4 1
2 5 1
4 7 1
5 8 1
1 3 1
3 6 2
6 9 2
9 10 1
9 11 2
11 12 1
11 13 1
*/