[Python] 백준 2533번: 사회망 서비스(SNS)

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

 

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline
TRUE, FALSE = 1, 0
INF = 1000001


def dfs(is_early_adapter, node, prev):
    # If dp already exists
    if dp[is_early_adapter][node] != INF:
        return

    adapter_count = is_early_adapter

    if is_early_adapter == TRUE:
        for n in graph[node]:
            if n == prev:
                continue

            dfs(TRUE, n, node)
            dfs(FALSE, n, node)

            adapter_count += min(dp[TRUE][n], dp[FALSE][n])

    else:
        for n in graph[node]:
            if n == prev:
                continue

            dfs(TRUE, n, node)

            adapter_count += dp[TRUE][n]

    dp[is_early_adapter][node] = adapter_count


if __name__ == '__main__':
    # Input
    N = int(input())
    graph = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # Add root
    graph[0].append(1)

    # Set dp
    dp = [[INF]*(N+1) for _ in range(2)]
    dfs(TRUE, 0, 0)

    # Print result
    print(dp[1][0] - 1)

 

DP[is_early_adapter][node]의 의미를 설명하기에 앞서, is_early_adapter는 TRUE(1), FALSE(0)으로 나뉜다는 것을 알아야한다. 아무튼, DP[1][7]는 노드 7이 얼리어뎁터일 때의 모든 얼리어뎁터의 갯수를 나타낸다.

 

그리고 이것을 기반으로 DFS 탐색을 시작하게 된다. 문제에 의하면,

 - 현재 노드가 얼리어뎁터라면 -> 다음 노드는 얼리어뎁터 / 일반 노드

 - 현재 노드가 일반 노드라면 -> 다음 노드는 얼리어뎁터

라는 경우의 수로 강제된다. 이를 이용하여 재귀 함수를 짜면 된다.

 

그리고 싸이클이 형성되지 않게끔 입력이 주어진다고 하였으므로, is_visited와 같은 리스트로 방문을 체킹하지 않아도 된다. 대신, 이전 노드를 저장(prev)하여, 그것을 제외하고 탐색을 하면 된다.

 

탐색 함수 인접노드를 모두 돌았다면 인접노드들에 해당하는 DP에는 해당 노드의 최소 얼리어뎁터 갯수가 있을 것이므로, 이것들을 모두 더해주면 된다. 마지막으로 더해준 값(adapter_count)을 현재 탐색 중인 노드의 DP에 넣어주면 재귀함수 설계가 완료된다.

 

우리는 0이라는 루트 노드부터 탐색을 시작하였고, 이것을 얼리어뎁터라고 가정하고 탐색을 시작한다.(얼리어뎁터일 경우 다음 노드가 얼리어뎁터일 때, 일반 노드일 때를 모두 고려하므로) 따라서 DP[1][0]에서 1을 뺀 뒤 이것을 출력해야한다.