[BOJ] 1949 - 우수 마을 (Python)

 

 

아이디어

 

DFS로 각 마을을 우수 마을로 선정했을 때와 선정하지 않았을 때 가능한 최댓값을 구해 나간다.

 

 

풀이

 

마을의 주민 수를 리스트 P에 저장하고, 마을 간의 연결을 2차원 리스트 graph에 저장한다.

dp[i][j]는 i번 마을을 루트 노드로 하여 해당 마을을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최댓값을 저장한다.

 

함수 dfs는 DFS로 마을을 차례로 방문하여 리스트 visited에 방문 표시 후 리프 노드부터 dp 테이블을 채워 나간다.

현재 마을을 우수 마을로 선정하지 않을 때는 연결된 마을의 우수 마을 여부와 상관없이 더 큰 최댓값을 더하고,

현재 마을을 우수 마을로 선정할 때는 연결된 마을이 우수 마을이 아닐 때의 최댓값을 더한다.

 

1번 마을을 루트 노드로 함수 dfs를 호출한 후, 1번 마을의 마을 주민 수 최댓값을 출력한다.

 

import sys

sys.setrecursionlimit(10002)
input = sys.stdin.readline

def dfs(idx):
    dp[idx][1] = P[idx]
    visited[idx] = 1
    for i in graph[idx]:
        if not visited[i]:
            dfs(i)
            dp[idx][0] += max(dp[i])
            dp[idx][1] += dp[i][0]

N = int(input())
P = [0]+list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
dp = [[0]*2 for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
dfs(1)
print(max(dp[1]))

 

 

재귀 한도를 10,001 이하로 설정하면 RecursionError가 발생했다.

# 런타임 에러 코드
import sys

sys.setrecursionlimit(10001)