C++ 백준 20171 (Dessert Cafe)

백준 20171 (Dessert Cafe)

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

20171번: Dessert Café

---

일단 N개의 노드에서 항상 N-1개의 간선이 주어지므로 스패닝트리로 볼 수 있다.

이 문제에서는 간선의 가중치는 중요하지 않다. 왜그런지 테스트케이스 1번을 예시로 들어보겠다.

 

설명

---

테스트케이스 1번에서 주어진 그래프이다. 위에서 말했듯이 인풋은 항상 스패닝트리로 주어지기 때문에 길게 늘어뜨려서 위와같은 모양을 만들 수 있다.

위 예제에서 good place가 될 수 있는 지점은 다음과 같다.

뭔가 보이지 않는가? good place가 되기 위한 지점은 apartment complexes(이하 ac)거나 ac사이의 노드들이다. 즉 good place가 되기 위해선 자신으로부터 최소 두가지 경로로 파생되는 path에 ac가 있어야 한다.

생각해보면 간단하다.어떤 한 지점에서 한방향으로만 ac가 존재한다면 그 지점은 ac로 가는 길(ac 포함)에 존재하는 노드들보다 ac에서 멀기 때문일 것이다. 말로 설명하기 힘들어서 그림을 통해 설명하자면 다음과 같다.

내가 현재 2번이라고 하자. 

오직 한방향으로 존재하는 ac(4번)으로 가는 path에선 3번노드와 4번노드가 있다.

그러나 2번노드는 d(3,4)와 d(4,4)보다 클것이므로 현재 이상황에선 절대 good place가 될 수 없다. (물론 1,3,5도 마찬가지)

그러나 다음과 같은 상황으로 바뀌었다고 생각해보자.

내가 현재 2번에 있다면, ac로 가는 두가지 길이 형성되었다. (1과 4)

위에서는 d(2,4)는 d(3,4)와 d(4,4)보다 컸기 때문에 good place가 되지 못했지만 다른 방향의 ac로 가는길이 생겼기 때문에 3번과 4번노드를 1번 ac로 기준으로 비교가 가능해진다.

즉 d(2,1)은 d(3,1)과 d(4,1)보다는 무조건 작기 때문에 위에서 3번과 4번노드에 대하여 조건이 충족되지 못했던 것을 상쇄시켜준다.

 

정리하자면 어떤 노드가 ac라면 당연히 good place이고 ac가 아니라면 두가지 이상의 path로 뻗어갔을 때 이 path들에서 ac가 나타나야 한다.

 

즉, ac들 사이에 있는 노드들이 good place이다.

이제 왜 간선의 가중치는 상관이 없는지 이해가 될것이다.

 

구현

---

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n,k;
vector <vector <int>> graph;
int res=0;
bool visit[100001];
bool ac[100001];

bool go(int curr){
    visit[curr]=true;
    bool findac = false;
    for(int i=0;i<graph[curr].size();i++){
        int dst = graph[curr][i];
        if(visit[dst]) continue;
        if(ac[dst]) findac = true;
        else if(!visit[dst]) {
            if(go(dst)) findac=true;
        }
    }
    if(!findac && !ac[curr]) return false;
    res++;
    return true;
}


int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>k;
    graph.resize(n+1);
    memset(visit,false,sizeof(bool)*(n+1));
    memset(ac,false,sizeof(bool)*(n+1));
    int a,b,c;
    for(int i=1;i<n;i++){
        cin>>a>>b>>c;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=0;i<k;i++){
        cin>>a;
        ac[a]=true;
    }
    for(int i=1;i<=n;i++){
        if(ac[i]) go(i);
    }
    cout<<res;
    return 0;
}