백준 - 1949

문제 설명

• N개의 마을이 있고, 마을 사이에 N-1개의 길이 존재한다.
• 길로 직접적으로 연결된 마을은 서로 인접한 마을이라고 한다.
• N개의 마을 중 우수 마을을 선정하려 하는데, 조건이 존재한다.

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
   
   
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
   
   
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

• 입력: 마을 수, 주민 수, 이어진 길(간선)
• 출력: 우수마을을 선정하는 경우의 수 중 가장 많은 주민 수

초기 접근방식

단순히 dp처럼 접근했지만, 모든 경우의 수(우수 마을과 인접한 상태 등)를 고려하기엔 어려웠다.

해결방안

dp배열을 선언할 때, 2차원 배열을 이용해 선언함으로써 물리적으로 우수마을인 경우와 우수마을이 아닌 경우를 분리해 생각했고, dfs를 이용한다.

또한, 트리의 특성에 기반하여

• 루트마을이 우수마을이 아닌 경우 자식마을이 우수마을이 되고
• 루트마을이 우수마을인 경우 자식마을은 우수마을이 될 수 없다.
  
  -> (인접한 마을은 서로 우수마을이 불가능)

코드에서는 아래와 같이 나타낸다.

• dp[마을][0] : index에 해당하는 마을이 우수마을이 아님
• dp[마을][1] : index에 해당하는 마을이 우수마을 임

작성한 코드

import sys
sys.setrecursionlimit(10**6) # Recursion Error 방지
input = sys.stdin.readline

def dfs(node):
    visit[node] = True       # 노드 방문 처리 (재방문 안하기 위해)

    for i in vil[node]:      # 간선이 존재하는 모든 노드에 대해
        if not visit[i]:     # 방문 안했으면 dfs 수행
            dfs(i)
            # dp[node][0] : dp[node]가 우수마을이 아닌 경우 
            # 자식 상태 중 큰 값 추가 
            dp[node][0] += max(dp[i][0], dp[i][1])
            
            # dp[node][1] : dp[node]가 우수마을인 경우 
            # 자식이 우수가 아닌 상태의 값 추가
            dp[node][1] += dp[i][0]                 

n = int(input())

visit = [0 for _ in range(n+1)] # 방문 여부 배열
vil = [[] for _ in range(n+1)]  # 인접 마을 배열

# 인구수를 받기 위한 배열, 계산 편의를 위해 [0]을 추가
population = [0] + list(map(int, input().split())) 

# [우수마을이 아닌 경우, 우수마을인 경우]를 위한 dp 배열
dp = [[0, population[_]] for _ in range(n+1)]          


for i in range(n-1):                                
    a, b = map(int, input().split())
    vil[a].append(b) # 인접 마을 추가
    vil[b].append(a)

dfs(1)

# dp[1]을 수행했으니, dp중 큰 값 출력 
print((lambda a, b : max(a, b))(dp[1][1], dp[1][0]))                      

디버깅 과정

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