[백준 Gold 1] 1949 우수 마을 - Java

문제링크 : https://www.acmicpc.net/problem/1949

1949번: 우수 마을

 

접근 과정 : 

• 특정 마을이 우수 마을인지 아닌지를 기준으로하는 DP를 사용했다.
• DP[][] : i 마을이 우수 마을인 경우(1)  / 우수 마을이 아닌 경우(0)  의 우수 마을들의 인구 총합
• 마을간의 연결 관계는, town 클래스를 생성해서 사용했다.
• '트리에서의 다이나믹 프로그래밍' 을 풀어보았다면 어렵지 않게 해결할 수 있다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    우수 마을

*/

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

public class BOJ1949 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        init();

        findDP(1);

        System.out.println(Math.max(dp[1][0], dp[1][1]));

    }

    private static class town {
        int num;
        town aside;

        town(int num, town aside) {
            this.num = num;
            this.aside = aside;
        }
    }

    static int N;
    static int[] population;
    static town[] towns;
    static boolean[] visit;
    static int[][] dp;

    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        population = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            population[i] = Integer.parseInt(st.nextToken());
        }

        towns = new town[N + 1];

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            insert(a, b);
            insert(b, a);
        }

        visit = new boolean[N + 1];
        dp = new int[N + 1][2];
    }

    static void insert(int a, int b) {

        if (towns[a] == null) {
            towns[a] = new town(b, null);
        } else {
            towns[a] = new town(b, towns[a]);
        }

    }

    static void findDP(int n) {

        visit[n] = true;
        dp[n][1] = population[n];

        town s = towns[n];

        while (s != null) {

            if (visit[s.num]) {
                s = s.aside;
                continue;
            }

            findDP(s.num);

            dp[n][0] += Math.max(dp[s.num][0], dp[s.num][1]);
            dp[n][1] += dp[s.num][0];

            s = s.aside;
        }
    }
}

 

P.S 

이전에 풀었던 문제와 상당히 유사했다.

 

https://rays-space.tistory.com/78 

[백준 Gold 3] 2553 사회망 서비스(SNS) - Java