[골드4] 14267. 회사 문화 1 (Java)

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

14267번: 회사 문화 1

칭찬 말고 인센 주세요~~

---

※  문제를 요약하면 아래와 같습니다.

▶ 어떤 회사에 매우 좋은 문화가 있는데 상사가 직속 부하를 칭찬하면 막내까지 내리 칭찬을 계속함

       (이 정도면 괴롭힘아닌가?)

▶  직속 상사와 직속 부하 관계가 그래프 형태로 주어짐

▶  모든 칭찬에는 칭찬의 정도를 의미하는 수치가 존재

▶  칭찬을 받은 정보가 주어진 후, 모든 직원이 얼마나 칭찬 받았는지 출력

▶  1번 직원은 사장님이라 칭찬 해줄 상사가 없음

▶  Input : 첫째줄에 직원 수 n명, 최초 칭찬 횟수 m 입력 ( 직원은 1번부터 n번까지 번호)

                  둘째줄에는 1번~N번까지 해당 번호의 직원의 직속 상사 번호가 공백을 구준으로 입력

                  이후 M줄에는 직속 상사로부터 칭찬을 받은 직원 번호, 칭찬의 수치가 주어짐

▶  Output : 1번 부터 N번까지 칭찬을 받은 정도를 출력

---

◈ Input - 1

5 3
-1 1 2 3 4
2 2
3 4
5 6

◈ Output - 1

0 2 6 6 12

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 각 직원의 칭찬 정보를 1차원 배열로 저장

▶ 그래프에서 어떤 노드의 다음 레벨에 대한 정보를 인접리스트로 구현

▶ 칭찬 정보가 들어올 때 마다 dfs탐색하여 더하면 무조건 시간 복잡도 2초 초과 ( N과 M은 최대 100000까지 입력) 

▶ 각 노드 (직원) 별로 칭찬 값을 미리 들고 있는 다음, DFS에서 다음 레벨 탐색 시 부모 노드의 칭찬 값 추가 

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int[] narrCompliments;
	static ArrayList<Integer>[] arrList;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		arrList = new ArrayList[N+1];
		narrCompliments = new int[N + 1];
		
		// 인접리스트 초기화
		for(int i = 0; i <= N; i++) {
			arrList[i] = new ArrayList<>();
		}


		// 직속 상사 입력 받아주고
		st = new StringTokenizer(bReader.readLine());
		for (int i = 1; i <= N; i++) {
			int nSenior = Integer.parseInt(st.nextToken());
			// DFS 관계 저장 ( 인접리스트 )
			if (nSenior != -1) {
				arrList[nSenior].add(i);
			} 
		}

		// 칭찬 받은 직원 부터 DFS 탐색 진행 후 해당 칭찬 수 미리 추가
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bReader.readLine());
			int nPerson = Integer.parseInt(st.nextToken());
			int nCompliment = Integer.parseInt(st.nextToken());

			// 미리 더해놓자.
			narrCompliments[nPerson] += nCompliment;
		}
		
		DFS(1);
		
		for (int i = 1; i <= N; i++)
			bWriter.write(narrCompliments[i] + " ");

		bWriter.flush();
		bWriter.close();
	}

	public static void DFS(int nIndex) {
		// 기저 조건
		for(int i = 0; i < arrList[nIndex].size(); i++) {
			int nChild = arrList[nIndex].get(i);
			// 누적합 고고하자
			narrCompliments[nChild] += narrCompliments[nIndex];
			// 다음 자식 노드 고고
			DFS(nChild);
		}
	}
}

Good Luck! (피드백 감사합니다!)