[ 백준 2533 ] 사회망 서비스(SNS) (C++)

백준의 사회망서비스(SNS)(2533) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

모든 사람이 새로운 아이디어를 수용할 수 있게끔 최소 얼리어답터의 수를 구해야 하는 문제이다.

본인이 문제를 해결한 과정대로 접근하는 방법에 대해서 이야기 해보자.

#1. 정점 연결 및 맵 생성

가장 먼저 누구와 누구가 연결되어있는지 알아야 한다.

즉, 어떤 정점들 끼리 연결되어있는지 알고 있어야 한다. 본인은 이를 Vector를 이용해서 표현해 주었다.

구체적으로는 Vector배열을 이용해서 표현해 주었다.

만약 정점 'A'와 정점 'B'가 연결되어 있다면, Vector[A].push_back(B) , Vector[B].push_back(A) 이런식으로

서로 연결되어 있는 정점을 벡터를 이용해서 관리해 주었다.

또한, 이 때 간선은 무방향성이기 때문에 A와 B가 연결되어 있다면 B와 A가 연결되어 있다고도 표현을 해주어야 한다.

두번째로는 1차적으로 정점간의 연결상황을 만들어 놓은 Vector를 이용해서 실제 트리 형태의 맵을 만들어 주었다.

깊이우선탐색 방법을 이용해서 만들어 주었다. 가장 첫 시작 정점은 '1'번정점으로 , 즉, 1번 정점을 루트노드라 생각하고 만들어 주었다.

#2. 정답 도출

본격적인 풀이는 완전탐색과 Dynamic Programming을 합쳐서 구현하였다. 완전탐색 중에서도 깊이 우선탐색(DFS)을 이용해서 접근하였다.

그 전에 지금부터 사용할 수식 한가지에 대해서 알아보자.

F[A][B] = C 라는 수식을 사용할 것인데, 먼저 'B'는 크기가 2칸 짜리인 배열이다. 왜냐하면 여기에는 '0' 혹은 '1'의 값만 들어갈 것이기 떄문이다.

F[A][0] = C 의 의미는 "현재 A번 정점이고, A번정점이 얼리어답터가 아닐 때, 최소 얼리어답터의 수는 C개입니다." 를 의미한다.

F[A][1] = C 의 의미는 "현재 A번 정점이고, A번정점이 얼리어답터일 때, 최소 얼리어답터의 수는 C개입니다." 를 의미한다.

그리고 이 수식을 이용해서 최소값을 도출해볼 것이다.

먼저, 이 수식의 초기값을 모두 -1로 초기화 시켜 주었다. F[A][B] = -1의 의미는 아직 계산이 되어지지 않은 상태를 의미한다.

이 후, DFS를 이용해서 탐색을 진행할 것인데, 매개변수로는 [ 현재 정점 , 현재 상태 ] 를 호출하게 된다.

즉, 현재 정점을 얼리어답터로 설정할 것인지 아닌지 판단하기 위해서 위와 같이 2가지 변수를 호출하게 된다.

그럼 가장 첫 호출은 어떻게 해주어야 할까 ? 1번 정점을 루트노드로 가정한다면 다음과 같이 2번을 호출해 주어야 한다.

DFS(1 , 0) , DFS(1 , 1)

DFS(1 , 0)이 의미하는 것은 "현재 1번 정점이고, 이 정점을 얼리어답터가 아닌 정점으로 설정하겠습니다." 를 의미하고,

DFS(1 , 1)이 의미하는 것은 "현재 1번 정점이고, 이 정점을 얼리어답터인 정점으로 설정하겠습니다." 를 의미한다.

1번 정점을 얼리어답터로 설정 할지 안할지에 따라서 결과값이 달라질 수 있기 때문에 이 2가지 상황 모두 탐색해 보아야 한다.

탐색을 진행할 때에는, 2가지 상황을 생각해 주면 된다.

1. 만약 현재 정점이 얼리어답터라면 ?

현재 정점이 얼리어답터라면, 이 현재 정점과 연결되어 있는 정점들은 얼리어답터가 되어도 되고, 안되어도 상관이 없다.

즉, 연결되어 있는 정점들로 넘어가기 위해서 탐색을 할 때, 위의 2가지 상황을 모두 탐색해 주는 것이다.

연결되어 있는 정점도 얼리어답터로 설정하는 경우, 연결되어 있는 정점을 얼리어답터로 설정하지 않는 경우.

이 2가지 경우를 모두 비교한 후에 더 최소값으로 값을 저장해 주면 된다.

2. 만약 현재 정점이 얼리어답터가 아니라면 ?

현재 정점이 얼리어답터가 아니라면, 이 현재 정점과 연결되어 있는 정점들은 반드시 얼리어답터여야 한다.

그래야 현재 정점 또한 아이디어를 전파 받을 수 있기 때문이다.

따라서 이 경우에는 다음 정점으로 넘어가기 위해서 탐색을 할 때, 연결되어 있는 정점들은 반드시 얼리어답터가 되도록

탐색을 진행하면 된다.

[ 소스코드 ]

#include <iostream>
#include <vector>
#include <cstring>
 
#define endl "\n"
#define MAX 1000010
using namespace std;
 
int N;
int Memo[MAX][2];
vector<bool> Visit;
vector<int> V[MAX];
vector<int> Tree[MAX];
 
int Min(int A, int B) { return A < B ? A : B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N - 1; i++)
    {
        int a, b; cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    Visit.resize(MAX, false);
}
 
void Make_Tree(int Cur)
{
    Visit[Cur] = true;
    for (int i = 0; i < V[Cur].size(); i++)
    {
        int Next = V[Cur][i];
        if (Visit[Next] == false)
        {
            Tree[Cur].push_back(Next);
            Make_Tree(Next);
        }
    }
}
 
int DFS(int Cur, int State)
{
    if (Memo[Cur][State] != -1) return Memo[Cur][State];
    if (State == 1)
    {
        Memo[Cur][State] = 1;
        for (int i = 0; i < Tree[Cur].size(); i++)
        {
            int Next = Tree[Cur][i];
            Memo[Cur][State] += Min(DFS(Next, 0), DFS(Next, 1));
        }
    }
    else
    {
        Memo[Cur][State] = 0;
        for (int i = 0; i < Tree[Cur].size(); i++)
        {
            int Next = Tree[Cur][i];
            Memo[Cur][State] += DFS(Next, 1);
        }
    }
    return Memo[Cur][State];
}
 
void Solution()
{
    Make_Tree(1);
    memset(Memo, -1, sizeof(Memo));
    int Result = DFS(1, 0);
    int Result2 = DFS(1, 1);
    
    cout << Min(Result, Result2) << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}