[BOJ] 백준 1949번 우수 마을 (Java)

#1949 우수 마을

난이도 : 골드 1

유형 : 트리 순회/ DP

1949번: 우수 마을

▸ 문제

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.

이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.

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

각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

 

▸ 출력

첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력한다.

 

 

 

문제 풀이 🖋  

트리 DP문제로 카카오 기출에도 나온적이 있는 유형이다. 해당 문제는 Tree구조로 구성되어있는 마을 데이터를 dfs와 dp로 탐색하여 마을 인원 수가 최대가 되게 '우수마을'들을 선정하는 문제이다.

 

이 문제에서 유의할 점은 1번을 시작 노드로 설정하되 루트 노드로 설정하면 안된다는 것이다.

 

 

만약 1번을 루트 노드로 인식하고 풀이하면 뭐가 문제일까?

 

→ 1번이 루트 노드라고 가정하면 1번과 같은 계층에 있는 노드는 없다는 뜻이다. 그래서 탐색을 할 때 1번 탐색을 시작으로 단방향으로 한

층씩 내려가면서 트리 탐색을 진행하면 된다.

일반적인 트리구조. 루트노드를 기준이로 단방향 탐색 가능

 

→ 1번이 루트 노드가 아니라고 가정하면 1번과 같은 계층에 있는 노드가 있을 수도 있기 때문에 단방향 탐색을 하면 안된다. 단방향으로 탐색하게 되면 아래 계층에서 다시 1번과 같은 계층으로 올라가는 탐색은 할 수 없기 때문이다. 

 

반례 그래프는 다음과 같다.

6->2로 가기위해서는 양방향 트리 탐색을 해야 한다.

 

따라서, 루트 노드를 문제의 조건에서 직접적으로 주어지지 않은 이상 트리를 단방향 탐색을 해서는 안된다.

(루트노드를 직접적으로 주어진 문제 예시보러가기)

 

 

📚 조건

 ∙ 트리의 정점의 수 n  (1<= n <= 10,000)

 ∙ 마을 i의 인구수 town[i] ( 1 <= i <= n, 1 <= town[i] <= 10,000)

 

 ❐ 우수마을 조건

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

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

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

 

 

여기서 DP문제 풀이하면 3번 조건은 고려하지 않고 문제를 풀어도 정답을 받을 수 있다.

 

차근차근 생각해보면 된다.

  1) N번째 마을이 우수마을이라면 N+1번째 마을은 우수마을 x

  2) N번째 마을이 우수마을 아니라면, N+1번째 마을은 우수마을이 될 수도 있고 안 될수도 있다.

  3) 마찬가지로, N+1번째 마을이 아니라면 N+2번째 마을은 우수마을이 될 수도 있고 안 될수도 있다.

  4) 하지만 최대 합을 구하는 것이 목적이므로, 연산과정에서 알고리즘은 무조건 N+1번째 또는 N+2번째 마을을 무조건 우수마을로 선정해야만 한다.

  5) 그렇게 되면 2번 조건을 만족하므로, 따로 3번 조건을 고려하지않아도 자동으로 충족된다.

 

☛ 정리하자면 최댓값을 구하는 탐색 알고리즘을 설계하면 따로 예외처리를 해주지 않아도 자동으로 된다는 뜻이다.

 

 

풀이는 두가지인데, 하나는 트리 순회에 초점을 맞춰서 직관적으로 코드를 짰고, 다른 하나는 DP 메모이제이션 형태에 맞춰 코드를 짰다.

 

 

 

첫 번째 풀이 (트리 순회, DFS) ✔︎ 

import java.io.*;
import java.util.*;

public class Main {

	static int[] town;
	static List<Integer>[] list;
	static boolean[] check;
	static int[][] memo;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int n = Integer.parseInt(br.readLine());
		
		town = new int[n+1];
		memo = new int[n+1][2];
		check = new boolean[n+1];
		list = new ArrayList[n+1];
		for(int i=0; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		for(int i=1; i<n+1; i++) {
			Arrays.fill(memo[i],-1);
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<n+1; i++) {
			town[i] = Integer.parseInt(st.nextToken());
		}
		
		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());
			
			list[b].add(a);
			list[a].add(b);
		}

		System.out.println(Math.max(traversal(1,0), traversal(1,1)+town[1]));
	}
	
	static int traversal(int pos, int flag) {
		
		if(list[pos].size()==0) return 0;
		if(memo[pos][flag] != -1) return memo[pos][flag];

		check[pos]= true;
		memo[pos][flag] = 0; 
		for(int child : list[pos]) {
			if(check[child]) continue;
			if(flag ==1 ) { // 이전 노드가 우수 마을일 경우 
				memo[pos][flag] +=traversal(child,0);
			}else {  // 이전 노드가 우수 마을이 아닐 경우 
				// dfs탐색으로 최대값 구하기 
				memo[pos][flag] +=Math.max(traversal(child,1)+town[child], traversal(child,0));
			}
			
		}
		check[pos]= false;
		return memo[pos][flag];
	}
}

 

 

 

두 번째 풀이 (DP, DFS) ✔︎ 

import java.io.*;
import java.util.*;

public class Main {

	static int[] town;
	static List<Integer>[] list;
	static int[][] dp;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int n = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		town = new int[n+1];
		dp = new int[n+1][2];
		for(int i=0; i<n+1; i++) {
			Arrays.fill(dp[i], -1);
		}
		for(int i=1; i<n+1; i++) {
			town[i] = Integer.parseInt(st.nextToken());
		}
		
		list = new ArrayList[n+1];
		for(int i=0; i<n+1; i++) {
			list[i] = 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());
			
			list[a].add(b);
			list[b].add(a);
		}

		System.out.println(Math.max(solve(1, -1, 1)+town[1], solve(1, -1, 0)));
		
	}
	static int solve(int pos, int prev, int flag) {
	
		int len =list[pos].size();
		
		if(dp[pos][flag] != -1) return dp[pos][flag];
		
		dp[pos][flag] =0;
		for(int i=0; i<len; i++) {
			int next = list[pos].get(i);
			// 왔던 길 반복 x 
			if(next != prev) {
				if(flag==1) { // 이전 노드(prev)가 우수 마을일 경우 
					dp[pos][flag] += solve(next, pos, 0); 
				}else { //이전 노드(prev)가 우수 마을이 아닐 경우
					// 이전 노드(prev)와 연결된 노드 중 우수 마을이 1개 나와야하므로 dfs탐색으로 최대값 구하기 
					dp[pos][flag] += Math.max(solve(next, pos, 1)+town[next], solve(next, pos, 0));
				}
			}
			
		}
		
		return dp[pos][flag];
	}
	
	
}

 

 

첫 번째 풀이 결과

두 번째 풀이 결과

 

사실 형태만 살짝 다를 뿐 성능은 똑같으니 익숙한 방식을 사용하면 될 것 같다. 그래도 난 트리 문제는 뭔가 첫 번째 풀이 방식이 더 편하고 쓰기 좋은 것 같다.

 

 

❍ 비슷한 유형 문제 추천

2213번: 트리의 독립집합

 

 

+ 트리 순회 카카오 기출 문제

* 해당 문제는 루트노드를 지정해줬기 때문에 단방향 탐색으로 풀이해도 된다.

 ❍ 문제 

코딩테스트 연습 - 매출 하락 최소화