BOJ - 우수 마을 1949번 (JAVA, Python)

❓ 문제 - 백준 우수 마을 1949번 - JAVA, Python 풀이법

 

출처 

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

1949번: 우수 마을

 

 

📝 문제해결법

1. 이 문제는 DFS + DP, Tree DP로 해결했다.

 

[문제의 조건] 

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.

2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을 모두 '우수 마을'로 선정할 수 없다. 즉 '우수 마을' 끼리는 서로 인접해 있을 수 없다.

3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

• dp[마을 번호][우수마을이 아닐 때=0], dp[마을 번호][우수 마을일 때 = 1]로 두고 dfs를 돌리면서 dp에 우수 마을 일때, 우수 마을이 아닐 때의 우수마을의 주민수의 최대값을 갱신한다.
• 3번은 딱히 고려할 필요가 없다.
• 문제에서 조건을 확인하면 우수마을끼리는 인접하면 안된다. 
• 따라서 현재 우수 마을(1)이라면, 인접한 곳은 우수 마을이 아닌(0) 상태이다.
• 그리고 현재 우수 마을이 아니라면(0), 인접한 곳은 우수 마을(1) 이거나 우수 마을이(0)이 아닌 상태이다.
• 위의 상태를 고려해서 dp값을 갱신한다. 

2. 느낀점

• 처음에 다익스트라인줄 알고 접근했다가,, 문제가 이해가 안갔었다.
• 코테를 볼 때마다 다익스트라와 DFS + DP OR 트리 DP를 헷갈렸는데 이런 문제를 풀어보니 약간은 감이 온 것 같다.
• 더 익숙해지게 다양한 문제를 풀어봐야겠다.

 

💻 소스코드 (JAVA)

// BOJ - 우수 마을(1949번)
// Tree DP


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_1949 {
	public static int n;
	public static int[] people;
	public static int[][] dp;
	public static boolean[] visited;
	public static ArrayList<ArrayList<Integer>> graph;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		people = new int[n+1];
		visited = new boolean[n+1];
		graph = new ArrayList<>();

		graph.add(new ArrayList<>());
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<n;i++) {
			people[i+1] = Integer.parseInt(st.nextToken());
			graph.add(new ArrayList<>());
		}

		for(int i=0;i<n-1;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		dp = new int[n+1][2];
		dfs(1);
		System.out.println(Math.max(dp[1][0], dp[1][1]));
	}

	public static void dfs(int x) {
		visited[x] = true;
		dp[x][1] = people[x];
		for(Integer i:graph.get(x)) {
			if(!visited[i]) {
				dfs(i);
				dp[x][0] += Math.max(dp[i][0], dp[i][1]);
				dp[x][1] += dp[i][0];
			}
		}
	}

}

 

💻 소스코드 (Python)

# BOJ - 우수 마을
# 트리 DP

import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline

n = int(input())
people = [0] + list(map(int, input().split()))
graph = [[] for i in range(n+1)]
dp = [[0, 0] for i in range(n+1)]
visited = [False for i in range(n+1)]


for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(x):
    visited[x] = True
    dp[x][1] = people[x]
    for i in graph[x]:
        if not visited[i]:
            dfs(i)
            dp[x][0] += max(dp[i][0], dp[i][1])
            dp[x][1] += dp[i][0]

dfs(1)

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