[C++] 2533 - 사회망 서비스(SNS) (골드3)

1. 문제 설명

 

요새 너무 바빠서 문제 하나 풀 여유조차 없다는 게 너무 서러워서 골드 문제라도 오랜만에 풀어봤다.

플래티넘은 푸는데 시간이 얼마나 소요될 지 감이 안 잡혀서 ㅠㅠ

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

---

2. 아이디어

 

이 문제를 처음 보자마자 vertex cover 문제로 접근하면 되겠구나 싶었다. (그러면 이분 매칭 문제로 바뀐다.)

 

하지만 조금 더 생각을 해보자.

가중치가 따로 존재하진 않으므로, 유량을 1로 전부 고정시키고 포스 풀커슨 알고리즘을 쓰면 효과적일 것이다.

하지만 포드 풀커슨 알고리즘의 시간복잡도는 O((|E|+|V|) * F)이므로, 정점 최대가 1,000,000임을 고려하면 시간 복잡도 선에서 막힐 확률이 높아진다.

 

그럼 다른 방법을 강구해야만 한다.

얼리 어댑터냐 아니냐를 찾으면 되는데, 트리 탐색은 dfs로 진행을 하면 될 것이다.

재귀로 진행을 하면서 탐색 효율성을 올리기 위해서 dp를 이용해 탐색 조건을 마련해야 한다.

 

우선 cache는 이차원 배열로 선언하여 [현재 노드][얼리어댑터 여부] = 하위노드 포함 얼리어댑터 수 정도를 메모이제이션 해주면 될 것 같고,

나머지 구상해야 하는 것들은 재귀 조건, 루트 노드가 얼리 어댑터인 경우 정도만 살펴주면 된다고 판단했다.

 

📌 재귀 조건

 

이 문제는 다행히 노드가 번호 순서대로 매겨져 있고, 고립되어 있는 Edge가 존재하지 않으므로 단순하게 1번 노드부터 탐색을 해도 문제가 없다. 심지어 사이클 또한 존재하지 않는다.

dfs 함수의 인자로 무엇을 받아야 하나 고민을 했는데, cache 값을 위해서라도 현재 노드(cur), 현재 노드 얼리어댑터 여부(flag)는 당연히 받아야 할 것이다.

문제는 이게 양방향 연결이다 보니, 현재 노드에 연결된 Edge에게 재귀 호출을 부르다 보면 무한 재귀에 빠질 수도 있으므로, 나를 호출한 이전 노드의 정보를 알기 위해 이전 노드(pre) 값도 인자로 받아온다.

즉, dfs함수는 다음과 같은 형태를 갖는다.

dfs(int cur, int pre, int flag)

 

호출을 할 때는 현재 정점에 연결된 정점을 탐색한다.

어차피 연결된 정점이 없다면 여기서 멈출 것이므로, 기저 지점에 도달했다는 별다른 탈출 조건은 필요로 하지 않는다.

하지만 호출을 할 때 주의해야 할 것이 있다.

 

현재 노드에서 다음 노드를 호출할 때, 무조건 다음 노드가 얼리 어댑터인 경우와 아닌 경우를 모두 탐색하면 안 된다.

왜냐하면, 현재 노드가 얼리 어댑터라면 다음 노드는 얼리 어댑터여도 되고, 아니어도 된다고 생각할 수 있지만,

현재 노드가 얼리 어댑터가 아니라면 다음 노드는 반드시 얼리 어댑터여야 하기 때문이다.

따라서, 현재 노드의 flag로 분기점을 정의할 수 있다..

(flag) ? min(dfs(nxt, cur, 0), dfs(nxt, cur, 1)) : dfs(nxt, cur, 1);

 

다음으로 중요한 것은 루트 노드의 얼리 어댑터 여부다.

탐색은 무조건 1번 부터 시작하므로, 0번이라는 가상 노드를 설정한다는 아이디어를 떠올려 볼 수 있지만,

고작 그 기능 하나 때문에 코드가 다소 지저분해질 수 있는 우려가 있다.

그렇게 하는 거나, dfs 탐색 시작 시점에서 1번 노드가 얼리 어댑터냐 아니냐 두 번 호출하는 거나 시간 복잡도 면에서 큰 차이가 없을 것이라 여겨진다.

따라서, 이 경우도 여타 다른 노드들 처럼 값을 합산하면 해결할 수 있는 문제였다.

 

요새 개발만 하다가 오랜만에 C++ 써서 이상한 곳에서 시간을 더 많이 빼았겼다. 😩

---

3. 코드

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

using namespace std;

vector<vector<int>> graph;
int cache[1000001][2];

int dfs(int cur, int pre, int flag) {
    if (cache[cur][flag] != -1) return cache[cur][flag];

    int sum = 0;
    for (int idx=0; idx < graph[cur].size(); idx++) {
        int nxt = graph[cur][idx];
        if (nxt == pre) continue;
        sum += (flag) ? min(dfs(nxt, cur, 0), dfs(nxt, cur, 1)) : dfs(nxt, cur, 1);
    }
    return cache[cur][flag] = (flag) ? sum+1 : sum;
}

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

    int n; cin >> n;
    graph.resize(n+1);
    memset(cache, -1, sizeof(cache)); // notion! glabal array initialize 

    for (int i=0; i<n-1; i++) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    cout << min(dfs(1, 0, 1), dfs(1, 0, 0)) << "\n";

    return 0;
}