[BaekJoon] 백준 1949번 우수마을

[BaekJoon] 백준 1949번 우수마을

 

🎈문제

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

💬설명

• 이차원 배열로 dp를 짜는건 아직 어려운 것 같다ㅜ
• dfs + dp로 풀어주면 되는 문제
• 파이썬에서는 재귀 함수 깊이에 제한이 있어서 sys.setrecursionlimit()을 통해 이를 풀어줘야 한다.

👩‍💻코드

# BaekJoon 1949.py
import sys

sys.setrecursionlimit(20000)
N = int(input())
people = [0] + list(map(int, input().split()))
visited = [False for _ in range(N + 1)]  # 방문여부 저장
s = [[] for _ in range(N + 1)]  # 연결리스트
dp = [[0] * 2 for _ in range(N + 1)]  # dp[n][1]: n번 마을을 우수마을로 선정했을 경우 우수 마을의 주민 수의 총합


def dfs(start):
    global visited, dp, people, s
    visited[start] = True
    dp[start][0] = people[start]  # start번을 우수마을로 선정했을 경우 주민 수 추가
    for i in s[start]:  # 연결된 모든 마을들에 대해서 rotate
        if not visited[i]:
            dfs(i)
            dp[start][0] += dp[i][1]  # 우수마을로 선정했을 경우 주변 마을은 우수마을로 선정x
            dp[start][1] += max(dp[i][0], dp[i][1])  # 우수마을로 선정하지 않았을 경우 주변 마을을 우수마을로 선정할지 결정


# 연결리스트 초기화
for _ in range(N - 1):
    a, b = map(int, input().split())
    s[a].append(b)
    s[b].append(a)

dfs(1)
print(max(dp[1][0], dp[1][1]))

 

👉참고

https://pacific-ocean.tistory.com/333