[Java] BaekJoon 1949. 우수마을(골드1) (DFS, DP)

문제출처: https://www.acmicpc.net/problem/1949

1949번: 우수 마을

 

문제이해

목표

N개의 마을로 이루어진 나라 (1~N)
이 나라는 최소 스패닝 트리(MST)로 모두 양방향 연결되어 있다.
조건1. 우수마을 끼리 인접해 있을 수 없다.
조건2. 우수마을로 선정된 마을은 적어도 하나의 우수마을과 인접해 있어야한다. 

이를 만족하면서 우수마을로 선정된 마을 주문수의 총합이 최대가 되도록 도출하여라

 

풀이

연결된 상태를 나태내는 인접리스트(adjList), 가격을 나타내는 배열(prices), 최대 구성원을 저장할 배열(dp[][])를 만들고

 

dp의 정보는 다음과 같다.

dp[현재마을 번호][현재마을 우수마을여부]  

 dfs로 탐색을 진행 할 건데, 조건을 먼저 확인해 보자.

 

먼저 우선적으로 

dp[now][1] = prices[now]   => 현재 마을이 우수마을이기 때문에 마을 주민 수를 더해준다.

dp[now][0] = 0   => 현재 마을이 우수마을이 아니기 때문에 마을 주민 수를 더해주지 못한다.

 

조건1에 따라, 

• dp[now][1] 인 경우 연결된 다음(next) 마을들은 모두 우수마을이 아니어야 한다.
  dp[now][1] += for ( sum(dp[next][0]) )
• dp[now][0] 인 경우 연결된 다음 마을들이 우수마을이어도 되고 아니어도 되기 때문에, 둘중 큰 값을 + 해준다.dp[now][0] += for ( Max(dp[next][0], dp[next][1]) )혹여, 조건2를 고려하여, 적어도 하나의 우수마을과 인접해야된다고 고려할 수 있는데, 어차피 최대 값을 저장하려 하기 때문에 우수마을은 최대한 많이 활용하여 하나도 없는경우는 존재한다고 알 수 있다. 

 

소스코드

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

public class 우수마을 {
    private static int N;
    private static ArrayList<Integer>[] adjList;
    private static int[] prices;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 설정
        N = Integer.parseInt(br.readLine());
        adjList = new ArrayList[N + 1];
        prices = new int[N + 1];
        dp = new int[N + 1][2]; //
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }
        // 가격
        String[] strArr = br.readLine().split(" ");
        for (int i = 1; i <= N; i++) {
            prices[i] = Integer.parseInt(strArr[i - 1]);
        }
        // 인접리스트
        for (int i = 0; i < N - 1; i++) {
            strArr = br.readLine().split(" ");
            int num1 = Integer.parseInt(strArr[0]);
            int num2 = Integer.parseInt(strArr[1]);
            adjList[num1].add(num2);
            adjList[num2].add(num1);
        }

        int answer = dfs(1, 0);
        System.out.println(answer);
    }

    private static int dfs(int now, int parent) {
        dp[now][0] = 0;
        dp[now][1] = prices[now];

        for (Integer next : adjList[now]) {
            if (next != parent) {
                dp[now][0] += dfs(next, now);
                dp[now][1] += dp[next][0];
            }
        }
        return Math.max(dp[now][0], dp[now][1]);
    }
}