백준 사회망 서비스(Python/Go)

문제 링크: www.acmicpc.net/problem/2533

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

 

dp+dfs로 풀이할 수 있는 문제입니다.

우선 본인이 얼리어답터가 아닐 때는 친구들은 얼리어답터일 수도 있고 아닐 수도 있습니다.
그러나 본인이 얼리어답터가 아니라면 친구들은 모두 얼리어답터여야 합니다.

얼리어답터인 경우와 아닌 경우를 따져야하므로 dp는 dp[i][0], dp[i][1] 이렇게 2차원으로 만듭니다.

dp의 값은 최소개수를 나타냅니다. 예를 들어 dp[1][0] 이라면 1번이 얼리어답터가 아닐 때 총 얼리어답터의 최소 개수입니다.

dfs(1)로 시작을 하면 bottom-up 방식으로 dp가 완성되어 dp[1][0]과 dp[1][1]에 각각 최소 개수가 들어있을 것이고 2개중 더 작은 값이 정답이 됩니다. (꼭 1로 시작을 해야하는건 아니지만 아래 코드에서는 1로 시작했습니다.)

아래는 Python 코드입니다. (그런데 백준에서 파이썬으로 제출하면 python3는 시간초과가, pypy3는 메모리초과가 나옵니다. 이유는 모르겠습니다.)

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
 
 
def dfs(x):
    visited[x] = 1
    dp[x][0] = 0  # 재귀로 들어온 후 얼리어답터가 아닐 때는 0으로
    dp[x][1] = 1  # 얼리어답터인 경우는 1로
 
    for i in graph[x]:  # x와 연결되어 있는 노드들 탐색
        if not visited[i]:
            dfs(i)
            dp[x][0] += dp[i][1]
            dp[x][1] += min(dp[i][0], dp[i][1])
 
 
n = int(input())
visited = [0]*(n+1)  # 1부터 시작하므로 n+1로 만들었음, 중복여부 체크
dp = [[-1]*2 for _ in range(n+1)]  # 위와 마찬가지로 n+1
graph = defaultdict(list)
for _ in range(n-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
 
dfs(1)
print(min(dp[1][0], dp[1][1]))

 

아래는 Go코드입니다. (Go로 제출하면 정상적으로 통과합니다.)

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
 
var visited []int
var dp [][]int
var graph [][]int
 
func GetMin(a, b int) int {
    if a >= b {
        return b
    }
    return a
}
 
 
 
func Dfs(x int) {
    visited[x] = 1  // 방문 체크
    dp[x][0] = 0  // 얼리어답터가 아닌 경우 (사실 golang 특성상 0으로 초기화되므로 안해줘도 되긴함)
    dp[x][1] = 1  // 얼리어답터인 경우에는 개수를 올려야하므로 1
 
    for _, node := range graph[x] {
        if visited[node] == 0 {
            Dfs(node)
            dp[x][0] += dp[node][1] // 얼리어답터가 아닌 경우에는 친구들이 다 얼리어답터여야 하므로 백트래킹 받은 값 더해줌
            dp[x][1] += GetMin(dp[node][0], dp[node][1]) // 얼리어답터인 경우에는 친구들이 두가지 가능하므로 최소값을 더해줌
        }
    }
}
 
 
func main() {
    var n int
    fmt.Scanln(&n)
 
 
    visited = make([]int, n+1) // 1부터 시작하므로 인덱스 편의상 n+1
    dp = make([][]int, n+1)
    for i:=0; i<n+1; i++ {
        dp[i] = make([]int, 2)
    }
    graph = make([][]int, n+1)
 
    scanner := bufio.NewScanner(os.Stdin)
    for i:=0; i<n-1; i++ {
            scanner.Scan()
            input := scanner.Text()
            nums := strings.Fields(input)
            u, _ := strconv.Atoi(nums[0])
            v, _ := strconv.Atoi(nums[1])
            graph[u] = append(graph[u], v)
            graph[v] = append(graph[v], u)
    }
 
    Dfs(1)
    fmt.Println(GetMin(dp[1][0], dp[1][1])) // 얼리어답터가 아닌 경우와 맞는 경우 중에 최소 값이 정답
}
 

go로 제출시 시간은 1320ms가 나옵니다.