[Algorithm]Baekjoon 2533번 :: 사회망 서비스(SNS)

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

2533번: 사회망 서비스(SNS)

 
 
int n, a, b;
vector<vector<int>> graph(1000001);
bool visited[1000001] = { false };
int answer = 0;
 
// 색칠은 1리턴, 안색칠 2리턴, 자식들 중 하나라도 리프노드있으면 3리턴
 
int DFS(int node)
{
    int childCount = 0;
    int earlyadopterChildCount = 0;
    int leafChildNodeCount = 0;
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int child = graph[node][i];
        if (visited[child]) continue;
 
        ++childCount;
        visited[child] = true;
        int result = DFS(child);
 
        if (result == 1)
        {
            ++earlyadopterChildCount;
        }
        else if (result == 3)
        {
            ++leafChildNodeCount;
        }
    }
 
    if (childCount == 0)
    {
        return 3;
    }
 
    if (earlyadopterChildCount == childCount)
    {
        return 2;
    }
    else
    {
        ++answer;
        return 1;
    }
 
    if (leafChildNodeCount > 0)
    {
        ++answer;
        return 1;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    graph.resize(n + 1);
 
    for (int i = 0; i < n-1; ++i)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    visited[1] = true;
    int num = DFS(1);
    if (num == 3) ++answer;
    cout << answer;
}
 

 

예전에 비슷한 문제를 풀었던 느낌이 기억나서 생각보다 쉽게 풀었다.

그래프의 모든 노드들은 이웃된 노드들 중 반드시 1개이상은 얼리어답터여야 한다.(편의상 색칠이라 했음)

내가 세운 원칙은 다음과 같다.

 

1. 자식들을 순회할 때, 하나라도 리프노드인게 발견되면 현재노드를 색칠하고 부모에게 색칠했다는것을 알리는 리턴을 한다.

     -> 자식이 하나라도 리프노드라면 반드시 해당 리프노드나 현재노드 둘 중 하나를 색칠해야 한다.

          리프노드는 색칠해봤자 혜택보는게 자기자신밖에 없기 때문에 무조건 부모인 현재노드를 색칠하는게 이득읻.ㅏ

 

2. 자식들을 순회할 때, 단 한개라도 안칠해져있으면 자신을 색칠하고 부모에게 색칠했다는것을 알리는 리턴을 한다.

     -> 이웃된 노드중 최소 1개는 반드시 색칠되어져야 하기 때문에, 자식들 중 1개라도 색칠이 안되어있다면 어쩔수없이 자신을 색칠하고 부모에게 색칠했다는 알림리턴을 한다. 

 

3. 자식들이 전부 색칠되어있다면, 비로소 자신은 색칠을 안해도되고 부모에게 색칠을 안했다는 알림리턴을 한다.

      -> 자식들이 전부 색칠되어있다면 굳이 자신을 색칠할 필요없다. 최소횟수를 구하는 문제이기 때문.

 

 

n값은 최대 100만(정점 최대 100만)이라 적은 값은 아니지만, 노드를 한번씩만 탐색하기 때문에 시간초과에 걸리지 않는다.

그리고 문제에서 주어진 그래프는 트리형태라고 알려져있긴한데 그렇다고 무조건 1번노드를 시작으로 쭉쭉 내려가면 안된다. 즉 처음에 간선정보를 입력받을 때 단방향이 아닌 양방향으로 입력받아야 한다.

그래야 아무 노드를 선택하고 탐색을 시작했을 때 정답을 구할 수 있다.

만약 단방향으로 한다면, 모든 노드에 DFS를 시작해야 한다.  하지만 그럴경우 무조건 시간초과가 걸리기 때문에, 어떤 노드를 기준으로 잡더라도 해당 노드가 루트노드인것처럼 동작하게 만들어야 한다.

양방향으로 해서 부모쪽으로도 타고흐를 수 있게 작성해야 한다.