[백준] 1949번 - 우수마을 / 골드 2 / 파이썬 풀이

문제 링크

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

1949번: 우수 마을

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• N 개의 마을로 이루어진 나라가 있는데, 각 마을에 1부터 N까지의 번호가 붙어 있음. (N은 입력으로 주어짐)
• 마을은 트리구조 = 마을과 마을 사이를 직접 잇는 N-1 개의 길이 있음. (A마을에서 B마을을 갈 수 있다. = B마을에서 A마을을 갈 수 있다.)
• 두 마을 사이에 직접 잇는 길이 있을 때 두 마을은 인접하다고 본다.
• '우수 마을'로 선정된 각 주민 수의 총합이 최대가 되어야 한다.
• 두 마을이 인접해 있다면 두 마을을 모두 '우수 마을'로 지정할 수 없다.
• '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과 인접해 있어야 한다.
  
  
• 문제 : 각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, '우수 마을'을 선정하고, 우수 마을의 총 주민수 합이 최대가 되도록 하는 프로그램 작성.
  
  
• 종료 조건
  - '우수 마을'에 대한 경우의 수에 따라서 총 주민 수가 모두 합산되고, 총 주민 수가 최댓값이 되었을 때 총 주민 수 출력하고 프로그램 종료.

 

입력

예제 입력 1

7
1000 3000 4000 1000 2000 2000 7000
1 2
2 3
4 3
4 5
6 2
6 7

 

출력

예제 출력 1

14000

---

풀이

예제 1번 도식화 / 주황색이 우수마을

 

"2가지 케이스를 모두 생각하고, 변수로서 구현하여 동적계획법을 적용시켜보자!"

import sys, collections

sys.setrecursionlimit(10 ** 6)  # 파이썬의 기본 재귀 깊이 제한을 늘려주기 위함.

n = int(sys.stdin.readline().strip())  # 마을의 개수 n 을 입력 받음.
citizen_num = [0] + [int(x) for x in sys.stdin.readline().split()]  # 주민 수 입력 받음.

g = collections.defaultdict(list)  # key 값을 null로 초기세팅하는 dict 자료형 선언
# '인접' 관계를 설정하기 위한 dict 자료형

for _ in range(n - 1):
    city_a, city_b = map(int, sys.stdin.readline().split())     # 문제에서 주어진 마을간 '인접' 관계 설정
    g[city_a].append(city_b)
    g[city_b].append(city_a)

visited = [0 for _ in range(n + 1)]		# 해당 마을을 계산에 넣었는지, 안 넣었는지 확인하기 위한 리스트 선언.

dp = [[0, citizen_num[i]] * 2 for i in range(n + 1)]  # 우수 마을의 총 주민 수 합을 구하기 위한 자료형 'dp' 선언.
# dp[i][0] = i 마을을 우수마을로 선정하지 않았으므로, 합산에 0이 선택됨.
# dp[i][1] = i 마을을 우수마을로 선정하였기 때문에, 합산에 해당 마을의 주민 수가 선택됨.


def dfs(cur):
    visited[cur] = 1  # 현재 살펴보고 있는 마을을 방문 처리.
    for u in g[cur]:    # 현재 살펴보고 있는 마을의 '인접'마을 원소들로 for문 반복.
        if not visited[u]:  # 한 번도 계산에 넣지 않은 마을이라면.
            dfs(u)
            dp[cur][1] += dp[u][0]  
		# 현재 마을을 우수마을로 선정한 경우
            # 현재 마을의 '인접 마을'이 우수 마을로 선정되지 않은 상태에서의 총 주민 수가 더해짐.

            dp[cur][0] += max(dp[u][0], dp[u][1])  
		# 현재 마을을 우수마을로 선정하지 않은 경우
            # 현재 마을이 우수마을로 선정되지 않았으므로, 
            # '인접 마을'이 우수마을인 경우와 우수마을이 아닌 경우 중에서 더 큰 값을 선택함.

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

 

참고

https://velog.io/@jini_eun/%EB%B0%B1%EC%A4%80-1949%EB%B2%88-%EC%9A%B0%EC%88%98-%EB%A7%88%EC%9D%84-Java-Python

[백준] 1949번 우수 마을 / Java, Python

https://cotak.tistory.com/29

[백준] 1949 - 우수 마을 [Python(파이썬)]