[백준] 1135번 '뉴스 전하기' - Java

https://www.acmicpc.net/problem/1135

1135번: 뉴스 전하기

---

문제

---

코드

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int n;
	private static int[] dp;
	private static ArrayList<Integer>[] tree;
	
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(bf.readLine());
		tree = new ArrayList[n];
		dp = new int[n];
		
		for(int i = 0 ; i < n ; i++) {
			tree[i] = new ArrayList<>();
		}
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		for(int i = 0 ; i < n ; i++) {
			int input = Integer.parseInt(st.nextToken());
			if(input != -1) {
				tree[input].add(i);				
			}
		}
		
		bw.write(dfs(0) + "\n");
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	public static int dfs(int cur) {
		int cnt = 0;
		int max = 0;
		PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
		for(Integer next : tree[cur]) {
			dp[next] = dfs(next);
			q.add(new int[] {next, dp[next]});
		}
		
		while(!q.isEmpty()) {
			int[] node = q.poll();
			cnt ++;
			max = Math.max(max, node[1] + cnt);
		}
		
		return max;
	}
}

 

Try1. 우선순위 생각하는것에 오류가 있었습니다.

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int n;
	private static int[] arr;
	private static ArrayList<Node> tree;
	private static int max = 0;
	
	public static class Node {
		int left = -1;
		int data;
		ArrayList<Node> children = new ArrayList<>();
		int time;
		int levelCnt = 0;
		
		public Node(int data, int left, int time) {
			this.data = data;
			this.left = left;
			this.time = time;
		}
		
		public void addChild(Node child) {
			children.add(child);
		}
	}
	
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(bf.readLine());
		arr = new int[n];
		tree = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		for(int i = 0 ; i < n ; i++) {
			int pn = Integer.parseInt(st.nextToken());
			if(pn != -1) {
				arr[pn] ++;
			}
			tree.add(new Node(i, pn, 0));
		}
		
		for(int i = n - 1 ; i > 0 ; i--) {
			Node now = tree.get(i);
			Node pn = tree.get(now.left);
			pn.addChild(now);
			pn.levelCnt = now.levelCnt + 1;
		}
		
		bfs(tree.get(0));
		
		bw.write(max + "\n");
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	public static void bfs(Node node) {
		ArrayList<Node> childSort = new ArrayList<>();
		childSort = node.children;
		childSort.sort((o1, o2) -> (arr[o2.data] + o2.levelCnt) - (arr[o1.data] + o1.levelCnt));
		int t = node.time;
		for(Node child : childSort) {
			t ++;
			max = Math.max(t, max);
			child.time = t;
			if(child.children.size() > 0) {
				bfs(child);
			}
		}
	}
}

---

Search

https://katastrophe.tistory.com/78