[BOJ 20171 // C++] Dessert Café

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 20171번 문제인 Dessert Café이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/20171

20171번: Dessert Café

문제에서는 각 노드간 거리를 입력으로 주지만, 이 문제를 해결하는 데에 각 노드간 거리는 필요하지 않다.

문제의 조건에 맞는 후보지 노드일 필요충분조건이 "어떤 두 아파트단지 사이를 있는 경로 위에 있는 점"이기 때문이다.

 

두 아파트단지를 잇는 경로 상에 있는 점의 경우 경로상 어느 쪽의 점을 골라도 두 아파트단지중 더 가까워진 아파트단지가 존재하므로, 저런 경로 위의 모든 점은 문제의 조건을 만족하는 후보지라는 것을 알 수 있다.

반면에, 어떤 경로 위에도 올라가 있지 못한 노드지점의 경우, 그 노드보다 다른 아파트단지가 더 가까운 노드가 존재한다는 것은 간단히 알 수 있다.

 

후보지를 찾기 위해, 주어지는 트리의 루트 노드를 입력으로 처음 들어오는 아파트단지로 하자.

또한, 이 노드를 후보지로 기록하자.

그 다음, 모든 노드에 대하여 부모노드가 무엇인지 dfs로 탐색하여 기록하자. (단 root node의 경우 자기자신으로 한다.)

그 뒤로, 남은 아파트단지를 입력받으면서, 부모노드가 후보지인 노드일 때까지 부모노드 방향으로 거슬러올라가며 그 노드가 후보지라고 기록하자. 부모노드가 후보지라면, 그 지점부터 후보지인 노드들을 따라 모든 다른 아파트단지까지의 경로들 위의 점들이 전부 조사되었음을 알 수 있다.

조사가 끝났다면, 후보지의 개수를 출력한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;

vector<int> G[100001];
bool candidate[100001];
int arrparent[100001];
int ans = 1;
int target;

void dfs(int root, int parent) {
    arrparent[root] = parent;
    vector<int>::iterator iter = G[root].begin();
    while (iter != G[root].end()) {
        if (*iter == parent) {
            iter++; continue;
        }
        dfs(*iter, root);
        iter++;
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K; cin >> N >> K;
    for (int i = 1;i < N;i++) {
        int x, y, z; cin >> x >> y >> z;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cin >> N; candidate[N] = 1; // 트리의 root노드를 N으로 잡음
    dfs(N, N);
    for (int i = 1;i < K;i++) {
        int temp;
        cin >> temp;
        while (!candidate[temp]) {
            candidate[temp] = 1;
            temp = arrparent[temp];
            ans++;
        }
    }
    cout << ans;

    return 0;
}