백준 2533번 사회망 서비스(SNS)

문제 링크입니다: https://www.acmicpc.net/problem/2533

알고리즘 자체는 쉬운 문제였는데 구현하는데 애를 먹었던 문제였습니다.

getEarlyAdaptor 함수 내에서 DFS를 같이 병행하려다 보니까 재귀가 돌면서 안에서 코드가 꼬인 것 같습니다.

그래서 DFS와 getEarlyAdaptor 함수를 불리하고 DFS를 통해 양방향 그래프를 단방향 그래프로 바꾼 뒤 답을 구했더니 잘 구해졌습니다.

여기서 단방향 그래프로 바꾸는 이유는 루트로부터 잎 노드(leaf node)까지 단방향으로만 확인하기 때문입니다.

알고리즘은 아래와 같습니다.

1. 본인이 얼리어댑터라면 자식은 얼리어댑터여도 좋고 아니여도 좋습니다.

2. 본인이 얼리어댑터가 아니라면 자식은 무조건 얼리어댑터여야 합니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring> //memset;

using namespace std;

 

const int MAX = 1000000 + 1;

 

int N;

vector<int> friends[MAX]; //처음 입력하는 친구 관계

vector<int> dirNode[MAX]; //단방향 그래프 저장

bool visited[MAX];

int cache[MAX][2]; //노드, earlyAdaptor?

 

//단방향 그래프로 바꾼다

void DFS(int nodeNum)

{

        visited[nodeNum] = true;

 

        for (int i = 0; i < friends[nodeNum].size(); i++)

        {

                 int next = friends[nodeNum][i];

                

                 if (!visited[next])

                 {

                         dirNode[nodeNum].push_back(next);

                         DFS(next);

                 }

        }

}

 

int getEarlyAdaptor(int nodeNum, bool early)

{

        int &result = cache[nodeNum][early];

        if (result != -1)

                 return result;

 

        //본인이 얼리어댑터이면 자식은 어떻든 상관없다

        if (early)

        {

                 result = 1; //얼리어댑터이므로

                 for (int i = 0; i < dirNode[nodeNum].size(); i++)

                 {

                         int next = dirNode[nodeNum][i];

                         result += min(getEarlyAdaptor(next, true), getEarlyAdaptor(next, false));

                 }

        }

        //본인이 얼리어댑터가 아니면 자식은 무조건 얼리어댑터여야한다

        else

        {

                 result = 0; //얼리어댑터가 아니므로

                 for (int i = 0; i < dirNode[nodeNum].size(); i++)

                 {

                         int next = dirNode[nodeNum][i];

                         result += getEarlyAdaptor(next, true);

                 }

        }

        return result;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N - 1; i++)

        {

                 int node1, node2;

                 cin >> node1 >> node2;

 

                 friends[node1].push_back(node2);

                 friends[node2].push_back(node1);

        }

 

        memset(cache, -1, sizeof(cache));

 

        DFS(1); //1이 루트

 

        //루트가 얼리어댑터일 수도 아닐 수도 있으므로

        cout << min(getEarlyAdaptor(1, false), getEarlyAdaptor(1, true)) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~