백준 14267번(JAVA)

기본적으로 트리를 생성할 줄 안다면 수월하게 풀 수있다.

나 같은경우에는 ArrayList로 트리를 구현했다.

문제에서는 직속부하와 상사라고 표현했지만

직속부하는 자식 노드, 상사는 부모 노드, 사장은 루트노드라고 생각하고 풀면된다.

우선 부모자식 관계를 입력받는다.

그 후 따로 선언해놓은 int[] result배열에 각각의 칭찬수치를 더한다.

예를들어 2번직원이 2만큼 칭찬받았다면 result[2]=result[2]+2, 

3번직원이 4만큼 칭찬받았다면 result[3]=result[3]+4, 이런식으로

그 후 사장노드부터 DFS를 실시하는데 실시할때 부모노드의 result값을 자식노드의 result값에 더한다.

그리고 result를 1부터 n까지 출력하면 끝.

핵심은 DFS를 사장부터 시작하고 부모노드의 result값을 자식노드의 result값에 더해주는것이다.

아래는 전체 소스코드이다.

소스코드

import java.util.*;
import java.io.*;
public class Main {

	public static int n;
	public static ArrayList<Integer>[] arr;
	public static int[] result;
	public static void DFS(int n,int value)
	{
		result[n]=result[n]+value;
		for(int i=0;i<arr[n].size();i++)
		{
			DFS(arr[n].get(i),result[n]);
		}
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] s=br.readLine().split(" ");
		n=Integer.parseInt(s[0]);
		int m=Integer.parseInt(s[1]);
		result=new int[n+1];
		arr=new ArrayList[n+1];
		for(int i=1;i<=n;i++)
		{
			arr[i]=new ArrayList<Integer>();
		}
		s=br.readLine().split(" ");
		for(int i=1;i<n;i++)
		{
			arr[Integer.parseInt(s[i])].add(i+1);//직속상사 관계 입력
		}
		for(int i=0;i<m;i++)
		{
			s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			result[a]=result[a]+b;
		}
		DFS(1,0);
		for(int i=1;i<=n;i++)
		{
			System.out.print(result[i]+" ");
		}//결과값 출력
	}
}

댓글과 지적은 언제든지 환영입니다~!

글이마음에들었다면 왼쪽 이미지를 눌러서 후원 부탁드립니다><