[백준] 알고리즘 분류(트리,JAVA)14267번, 회사 문화 1

문제 링크

14267번: 회사 문화 1

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 루트 노드는 항상 1번입니다.

2. 부모 노드는 항상 자식노드보다 번호가 작습니다.

3. 직속상사가 칭찬을 받으면 부하도 칭찬을 받으며 칭찬에는 수치가 존재합니다.

4. 모든 직원이 받은 칭찬의 수치를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 트리 구성 및 칭찬의 수치를 더해가는 DFS탐색을 진행합니다.

 

3. DFS으로 얻은 직원들이 받은 칭찬의 수치를 결과로 출력합니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5

M : 3

 

노드번호	1	2	3	4	5
직속 상사	-1	1	2	3	4
받은 칭찬 수치	0	2	4	0	6

 

 

2. 트리 구성 및 칭찬의 수치를 더해가는 DFS탐색을 진행합니다.

 

트리 구성.

칭찬의 수치

 

1	2	3	4	5
0	0	0	0	0

 

DFS 탐색.

1번 노드에는 받은 칭찬의 수치가 존재하지 않기 때문에 부하에게도 칭찬이 이어지지 않습니다.

 

칭찬의 수치(칭찬 누적값 : 0)

1	2	3	4	5
0	0	0	0	0

 

2번 노드에는 받은 칭찬의 수치 : 2

칭찬의 수치는 부하 직원들에게 누적되기 때문에 누적값이 증가합니다.

 

칭찬의 수치(칭찬 누적값 : 2)

1	2	3	4	5
0	2	0	0	0

3번 노드에는 받은 칭찬의 수치 : 4

칭찬의 수치는 부하 직원들에게 누적되기 때문에 누적값이 증가합니다.

3번 노드에 칭찬의 수치는 누적된 칭찬의 값까지 더해지기 때문에 2 + 4 = 6이 됩니다.

 

칭찬의 수치(칭찬 누적값 : 6)

1	2	3	4	5
0	2	6	0	0

4번 노드에는 받은 칭찬의 수치 : 0

4번 노드에는 받은 칭찬의 수치가 존재하지 않기 때문에 누적감이 증가하지 않습니다.

4번 노드에 칭찬의 수치는 누적된 칭찬의 값까지 더해지기 때문에 0 + 6 = 6이 됩니다.

 

칭찬의 수치(칭찬 누적값 : 6)

1	2	3	4	5
0	2	6	6	0

5번 노드에는 받은 칭찬의 수치 : 6

칭찬의 수치는 부하 직원들에게 누적되기 때문에 누적값이 증가합니다.

5번 노드에 칭찬의 수치는 누적된 칭찬의 값까지 더해지기 때문에 6 + 6 = 12이 됩니다.

칭찬의 수치(칭찬 누적값 : 6)

1	2	3	4	5
0	2	6	6	12

3. DFS으로 얻은 직원들이 받은 칭찬의 수치를 결과로 출력합니다.

 

0 2 6 6 12

결과로 출력됩니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리 및 칭찬의 정보를 띄어쓰기 기준 나누었습니다.
• 트리를 구성 및 칭찬의 수치 저장한 뒤 DFS함수를 실행하여 각 직원의 칭찬의 수치를 구하였습니다.
• 각 직원의 칭찬 수치를  BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• DFS함수는 부하 직원들을 탐색할 때 칭찬의 수치가 누적되도록 하였습니다.
• DFS함수는 DFS탐색을 통해서 루트 노드 1번부터 각 노드들을 탐색하여 칭찬의 수치를 구합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main{
    static int n,m;
    static int[] praise, answer;	//칭찬 수치 관련 배열
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();	//트리 관련 리스트
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        praise = new int[n+1];
        answer = new int[n+1];
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<=n;i++)
            tree.add(new ArrayList<>());
        st.nextToken();
        //트리 값 저장.
        for(int i=2;i<=n;i++){
            int parent = Integer.parseInt(st.nextToken());
            tree.get(parent).add(i);
        }
        //칭찬의 수치 저장.
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int p = Integer.parseInt(st.nextToken());
            int degree = Integer.parseInt(st.nextToken());
            praise[p] += degree;
        }
        //DFS 탐색.
        DFS(1, 0);
        //각 직원들의 칭찬 수치 BufferedWriter 저장
        for(int i = 1;i<=n;i++)
            bw.write(answer[i] + " ");

        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //칭찬의 수치가 누적되도록 진행되면서 DFS탐색을 진행하는 함수
    static void DFS(int cur, int degree){
        degree += praise[cur];		//칭찬 수치 누적
        answer[cur] = degree;		//칭찬 수치 저장
        //부하 직원들 탐색
        for(int child : tree.get(cur))
            DFS(child, degree);
    }
}