백준 20531 - 인간관계 [Python]

www.acmicpc.net/problem/20531

20531번: 인간관계

벨 수를 알고있으면 좋다.

 

union find를 활용한 dp문제이다. 차근차근 풀어보자

 

 

1. 점화식

dp[i][j] = (i개의 그룹을 j개로 묶는 경우의 수) 라고 하면,

dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1]

라고 점화식을 세울 수 있다.

나는 미리 dp 배열을 채워두고 시작했다.

 

2. 그룹의 수 세기

그룹의 개수를 n으로 두고 시작해보자.

두 사람이 입력으로 주어졌을때, 이 둘을 한 집합으로 합치는 과정에서 그 둘이 친구였는지를 확인할 수 있다.

둘이 친구가 아니었다면, n에 1을 빼주면 된다.

 

3. 답 구하기

i개의 그룹을 묶을 수 있는 모든 경우의 수를 구하는 것이니,

답은 sum(dp[n]) % mod 가 된다. (여기서 n은 앞에서 그룹의 수를 센 값이다.)

그룹의 수를 세기 위해서 union find를 사용하였다.

 

 

 

dp 배열 갱신을 잘못해서 계속 틀렸었다;;

 

Python 3으로는 시간초과가 뜬다.

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
mod = 10**9 + 7
for i in range(1, n+1):
    dp[i][1] = 1
 
for i in range(2, n+1):
    for j in range(2, i+1):
        dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1]) % mod
 
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
def union(x,y):
    global n
    x = find(x)
    y = find(y)
 
    if x != y:
        n -= 1
        p[y] = x
 
p = {}
for i in range(n+1):
    p[i] = i
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)
 
    print(sum(dp[n]) % mod)

글을 쓸 때마다 내 필력이 정말 안 좋다는걸 느낀다.......

 

오타, 오류 지적 환영합니다.