우수 마을 ( 1949 번 )

1949번: 우수 마을

 

---

🧠 알고리즘

• Tree DP (트리 동적 계획법)

 

✔️ 동작 방식

문제 핵심 아이디어
트리 형태의 마을 구조가 주어질 때, “서로 인접한 두 마을이 모두 우수 마을이 되면 안 된다”는 조건하에서 우수 마을들의 주민 수 합의 최댓값을 구하는 문제.

이를 위해 각 노드(마을)를 기준으로,

• dp[node][0] → 현재 노드가 우수 마을인 경우 최대 주민 수
• dp[node][1] → 현재 노드가 우수 마을이 아닌 경우 최대 주민 수
  를 저장한다.

점화식 (DFS 기반)

• 현재 노드가 우수 마을인 경우
  → 인접한 마을들은 우수 마을이 될 수 없음
• dp[node][0] = sum(dp[next][1]) + score[node]
• 현재 노드가 우수 마을이 아닌 경우
  → 인접한 마을들은 우수 마을이거나 아닐 수도 있음
• dp[node][1] = sum(max(dp[next][0], dp[next][1]))

DFS 탐색 순서

1. 1번 노드를 루트로 하여 DFS 수행
2. 각 자식 노드의 DP 값을 계산한 뒤, 부모 노드 DP에 반영
3. 모든 노드 방문 후 max(dp[1][0], dp[1][1])이 전체 최댓값

입출력 및 실행 과정 요약

1. n과 각 마을의 주민 수(score) 입력
2. _mk_conn()으로 인접 리스트 생성
3. _dfs(1)로 트리 순회 및 DP 계산
4. 결과 출력 → print(max(dp[1]))

---

 

🧾 코드

import sys
sys.setrecursionlimit(10**6)

def _mk_conn(num):
    answer = [[] for _ in range(num + 1)]
    for _ in range(num - 1):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        answer[a].append(b)
        answer[b].append(a)
    return answer


def _dfs(point):
    check[point] = False

    for next_point in conn[point]:
        if check[next_point]:
            _dfs(next_point)

            # 우수 마을
            dp[point][0] += dp[next_point][1]

            # 우수 마을 아님!!
            dp[point][1] += max(dp[next_point])

    
n = int(sys.stdin.readline().rstrip())
score = tuple(map(int, sys.stdin.readline().rstrip().split()))
"""
    dp >> [[우수마을, 우수마을 아님!!], ~~]
    우수마을 : 인접 마을의 우수마을 아닌 값 더해주기
    우수마을 아님 : 인접 마을 둘중 큰 값 더하기
"""
dp = [[0, 0] for _ in range(n + 1)]
for idx in range(n):
    dp[idx + 1][0] = score[idx]

conn = _mk_conn(n)
check = [True] * (n + 1)
_dfs(1)

print(max(dp[1]))

---

 

⏱️ 시간 복잡도

def _dfs(point) : 간선을 방문처리 하여 한번씩만 탐색 ( 선형 시간 복잡도 )
    check[point] = False
    
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )