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

30 Jul 2023 in Study on Coding Test

DFS와 DP를 사용해보는 문제

정답제출코드

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

struct Person
{
    bool visited = false;
    vector<int> link;
};

int dp[1000001][2];
int N;
vector<Person> Friends;

int m_min(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

void DFS(int a)
{
    Friends[a].visited = true;
    dp[a][1] = 1;

    for (size_t i = 0; i < Friends[a].link.size(); i++)
	{
		int Next = Friends[a].link[i];
		if (!Friends[Next].visited)
		{
			DFS(Next);		
			dp[a][0] += dp[Next][1];
			dp[a][1] += m_min(dp[Next][1], dp[Next][0]);
		}
	}
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 0; i <= N; ++i)
    {
        Person p;
        Friends.push_back(p);
    }

    for (int i = 0; i < N-1; ++i)
    {
        int a, b;
        cin >> a >> b;

        Friends[a].link.push_back(b);
        Friends[b].link.push_back(a);
    }

    
    DFS(1);

    cout << m_min(dp[1][0], dp[1][1]);

    return 0;
}

DP를 활용하여 푸는 문제라고 들었는데

아이디어가 떠오르지 않아서 참고링크를 참고하여 풀었다.

1번 노드부터 방문을 시작하며

dp[a][0], dp[a][1]의 의미는 각각 a번이 얼리어답터가 아닐 경우와 a번이 얼리어답터일 경우의 수이다.

따라서 dp[a][1] = 1은 우선 자신이 얼리어답터일 경우를 더해주는 것이다.

따라서 아래의 코드에서 dp[a][0]에는 다른 사람이 얼리 어답터일 경우를 더해주고,

dp[a][1]에는 dp[Next][0]과 dp[Next][1] 중에서 작은 경우의 수를 더해주면 된다.

void DFS(int a)
{
    Friends[a].visited = true;
    dp[a][1] = 1;

    for (size_t i = 0; i < Friends[a].link.size(); i++)
	{
		int Next = Friends[a].link[i];
		if (!Friends[Next].visited)
		{
			DFS(Next);		
			dp[a][0] += dp[Next][1];
			dp[a][1] += m_min(dp[Next][1], dp[Next][0]);
		}
	}
}

이렇게 순회를 마치고나서 1번 노드에 저장되는 값을 구해주면 된다.

사실상 탑-다운 형 dp문제였던 것 같다.

DP는 어려워..정말..