[Algorithm]Baekjoon 12978번 :: 스크루지 민호 2

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int n;
vector<vector<int>> graph(100001);
bool visited[100001] = { false };
int answer = 0;
 
bool DFS(int node)
{
    bool result = false;
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (visited[nextNode]) continue;
        
        visited[nextNode] = true;
        
        if (!DFS(nextNode)) // 하나라도 색칠안되어있으면
        {
            result = true;
        }
    }
 
    if (result) ++answer;
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    int start = 0;
 
    for (int i = 0; i < n-1; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        graph[a].push_back(b);
        graph[b].push_back(a);
 
        start = a;
    }
 
    visited[start] = true;
    DFS(start);
 
    cout << answer;
}
 
 

 

 

최소의 설치를 통해 반드시 두단계 이내에는 무조건 경찰서가 설치되어 있어야 하는 문제이다.

양방향 그래프이기때문에 어디 정점에서든 시작해도 상관없다. (최소 이 문제에 한해서는)

 

다시 위로 올라오는것을 방지하기위해 방문체크하면서 탐색할건데, 아래와 같은 로직을 거친다.

 

1. 일단 방문한 현재정점에 경찰서 설치 X.

2. 자식들 중, 하나라도 경찰서 설치가 안되어있으면 방문정점에 경찰서를 설치해야 한다.

3. 자식탐색 끝낸이후에 경찰서설치 되어있으면 ++answer.

 

끝이다. 로직은 매우 쉽다. 다만 그래프문제자체를 많이 안풀어봤을 때는 바로바로 떠올리긴 쉽지 않을수도있다.

경찰서를 일단 설치 안하고, 자식탐색이후에 경찰서 설치유무를 따지기 때문에 리프노드는 무조건 설치를 안하게 된다.

왜냐면, 경찰서설치는 최대한 미룰수록 이득이기 때문이다. 부모쪽으로 설치를 미룰수록 이득이다.

부모가 경찰서를 설치함으로써 다른 자식들이 설치안해도 되는 이득이 발생할 경우의 수가 증가하기 때문이다.