백준 27924 - 윤이는 엄청난 것을 훔쳐갔습니다 (C++)

문제

• 문제 링크

  
   BOJ 27924 - 윤이는 엄청난 것을 훔쳐갔습니다 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리와 윤이, 달구(경찰), 포닉스(경찰)의 시작 위치가 주어진다.
매 순간 윤이가 먼저 움직이고, 모두가 최선의 전략으로 추격전을 벌일 때 윤이가 탈출 할 수 있는 지의 여부를 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$3 ≤ N ≤ 200,000$

윤이, 달구, 포닉스의 시작 위치는 모두 다르다.

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 트리(trees)
• 깊이 우선 탐색(dfs)
• 그리디 알고리즘(greedy)

풀이

문제를 읽어가면서 동시에 다음의 생각이 떠올랐다.

시작 위치가 어떻던, 트리가 어떤 모양이던 간에 존재하는 모든 리프 노드에 대하여 $Dist_a < Dist_b$ && $Dist_a < Dist_c$를 만족하는 노드가 하나라도 있으면 되는거 아닌가?

만약 중간 이동 과정에서 위 조건이 뒤집히는 순간이 올 수 있는지에 대한 여부는 논리적으로 이뤄질 수 없는 게,
그래프가 트리임에 따라 반드시 최단 거리로 이동할테니 중간에 뒤집혔다면 리프 노드에서 역시 뒤집혀져 있어야 한다.

위는 $a, b, c$각 지점으로부터의 $dfs$를 돌려주면 되며, 리프 노드는 $indegree$를 이용해 쉽게 조사할 수 있다.

자세한 건 아래 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
#define N 200001
using namespace std;
 
vector <int> Gr[N];
int n, ind[N], dist[3][N];
 
void Input()
{
    cin >> n;
    for (int i, j, o{}; ++o < n;)
    {
        scanf("%d %d", &i, &j);
        Gr[i].push_back(j);
        Gr[j].push_back(i);
        ind[i]++, ind[j]++;
    }
}
void Init(int o, int now, int dis = 1)
{
    dist[o][now] = dis;
    for (int& i : Gr[now])
        if (!dist[o][i])
            Init(o, i, dis + 1);
}
int main()
{
    Input();
 
    int a, b, c;
    cin >> a >> b >> c;
    Init(0, a);
    Init(1, b);
    Init(2, c);
 
    for (int i(1); i <= n; i++)
        if (ind[i] == 1 && dist[0][i] < dist[1][i] && dist[0][i] < dist[2][i])
            cout << "YES", exit(0);
    cout << "NO";
}

comment

끝