BOJ_1623_신년 파티 (Java)

[Gold I] 신년 파티 - 1623

문제 링크

성능 요약

메모리: 147364 KB, 시간: 3040 ms

분류

다이나믹 프로그래밍, 트리, 트리에서의 다이나믹 프로그래밍

제출 일자

2025년 8월 20일 03:09:29

문제 설명

'주식회사 월드'의 조직도는 루트가 있는 트리 형태의 구조를 가지고 있다. 즉, 사장님을 트리의 루트로 하며, 직원들은 자신의 직속상관 바로 밑에 매달려 있는 형태가 된다.

김진영 부사장은 2008년 설을 맞아 '주식회사 월드'의 신년 파티를 계획 중에 있다. 단, 만일 부하직원이 자신의 직속상관과 파티에 함께 오게 되면 분위기가 경직될 수 있으므로, 파티의 분위기를 위해 부하직원과 그 직속상관은 같이 초대될 수 없도록 하려고 한다.

예를 들어 최백준 과장이 오민식, 오영식 대리의 직속상관이라고 하자, 만일 최백준 과장을 파티에 초대하려 한다면 오민식, 오영식 두 대리는 파티에 초대할 수 없다. 마찬가지로 오민식, 오영식 대리 중 어느 한 명이라도 파티에 초대하려 한다면 최백준 과장 역시 파티에 초대될 수 없다.

각 직원들의 "날라리 기질"은 평소 인사과의 관찰을 통해 회사의 데이터베이스에 기록이 되어 있다고 한다. 신년 파티의 "날라리 분위기"란 파티 참가자들의 "날라리 기질"의 합으로 정해진다.

김진영 부사장은 위의 제한을 만족시키면서 이번 신년 파티의 "날라리 분위기"를 최대화하도록 참가자 목록을 작성하려고 한다. 단, 사장의 참석 여부가 아직 불투명한 상황이기 때문에 사장이 참석하는 경우와 그렇지 않은 경우 각각에 대해 모두 참가자 목록을 결정해 줄 프로그램을 작성해야 한다. 아무도 초대하지 않는 경우 "날라리 분위기"가 최대일 수도 있다는 점에 주의한다.

입력

첫째 줄에 사장을 포함한 모든 직원의 수 N이 주어진다. (2≤N≤200,000) 사장은 1번이며, 다른 직원들은 2번부터 N번까지 차례로 번호가 매겨져 있다. 둘째 줄에는 사장을 포함한 모든 직원의 "날라리 기질"을 나타내는 N개의 정수가 빈 칸을 사이에 두고 1번 직원(사장)부터 N번 직원까지 순서대로 주어진다. 주어지는 정수는 절댓값이 10,000을 넘지 않는다. 셋째 줄에는 사장을 제외한 모든 직원의 직속 상관의 번호를 나타내는 N-1개의 정수가 빈 칸을 사이에 두고 2번 직원부터 N번 직원까지 순서대로 주어진다. 주어지는 수는 물론 N 이하의 자연수이며, 항상 루트가 있는 트리 형태의 구조를 갖도록 입력이 주어진다고 가정해도 좋다.

출력

첫째 줄에는 사장이 참석하는 경우와 그렇지 않은 경우의 "날라리 분위기"의 최댓값을 빈 칸을 사이에 두고 순서대로 출력한다. 둘째 줄과 셋째 줄에는 각각 사장이 참석하는 경우와 그렇지 않은 경우의 참가자 번호를 빈 칸을 사이에 두고 증가하는 순서대로 출력한다. 각 줄의 끝에는 -1을 추가로 출력해서 끝을 표시하도록 한다.

문제 풀이

dfs와 tree 구조를 사용했다.

백트래킹으로 경로도 탐색했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
	static int N;
	static int[] arr;
	static int[][] dp;
	static List<Integer>[] graph;
	static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1623_신년파티/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

		arr = new int[N+1];
		graph = new ArrayList[N+1];
		for(int i=0; i<N+1; i++) {
			graph[i] = new ArrayList<>();
		}
		dp = new int[N+1][2];

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

		st = new StringTokenizer(br.readLine());
		for(int child=2; child<=N; child++) {
			int parent = Integer.parseInt(st.nextToken());
			graph[parent].add(child);
		}

		dfs(1);

		sb.append(dp[1][1]).append(" ").append(dp[1][0]).append("\n");

		List<Integer> withBoss = new ArrayList<>();
		List<Integer> withoutBoss = new ArrayList<>();

		findPath(1, true, withBoss);
		findPath(1, false, withoutBoss);
		Collections.sort(withBoss);
		Collections.sort(withoutBoss);

		for(int w : withBoss) {
			sb.append(w).append(" ");
		}
		sb.append(-1).append("\n");
		for(int w : withoutBoss) {
			sb.append(w).append(" ");
		}
		sb.append(-1);

		System.out.println(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

	private void findPath(int i, boolean visited, List<Integer> res) {
		if(visited) {
			res.add(i);

			for(int g : graph[i]) {
				findPath(g, false, res);
			}
		}
		else{
			for(int g : graph[i]) {
				if(dp[g][1] > dp[g][0]){ // 부하 선택하는게 더 클 때
					findPath(g, true, res);
				}
				else{ // 부하 선택x 가 더 클 때
					findPath(g, false, res);
				}
			}
		}
	}

	private void dfs(int i) {
		dp[i][0] = 0;
		dp[i][1] = arr[i];

		for(int g : graph[i]) {
			dfs(g);
			dp[i][0] += Math.max(dp[g][0], dp[g][1]); // 본인안오면 부하는 오거나 안오거나
			dp[i][1] += dp[g][0]; // 본인 오면 부하는 못옴
		}
	}
}