[JAVA] 백준 14267 : 회사 문화 1

문제

14267번: 회사 문화 1

해결 방법

생각보다 까다로웠던 문제였다.

이 문제에서 주의 깊게 봐야 하는 것은 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이라는 것.

 

처음엔 인접리스트를 구현한 후에 칭찬을 받은 번호부터 칭찬의 수치를 dfs로 탐색하며 업데이트하는 방법을 사용했다.

다음 탐색할 곳을 찾는 것은 단순히 현재 탐색하는 곳보다 숫자가 크면 탐색하는 조건문을 사용했다.

하지만 최초 칭찬의 횟수만큼 계속 탐색을 진행하게 되어 시간 초과가 발생해서 다른 방법을 고민하였다.

 

통과된 방법은 최초 칭찬을 받은 만큼을 따로 credit 이라는 배열에 저장한 뒤에 dfs를 통해 result 배열에 한꺼번에 칭찬 횟수를 업데이트하는 방식을 사용했다.

그리고 한 사람이 여러 번 칭찬 받는 경우를 생각해서 칭찬 수치를 더할 때 기존 수치에서 추가를 해줘야 한다.

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
	static ArrayList<Integer> list[];
	static int credit[];
	static int result[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		credit = new int[n + 1];
		result = new int[n + 1];
		list = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		st.nextToken(); // 보스의 정보는 필요가 없어서 건너뜀.
		for (int i = 2; i <= n; i++) {
			int temp = Integer.parseInt(st.nextToken());
			list[temp].add(i);
			// 부하 직원한테 내리 칭찬하기 때문에 한 방향만 입력함.
		}
		
		for (int j = 0; j < m; j++) {
			st = new StringTokenizer(br.readLine(), " ");
			int i = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			credit[i] += w; // 한 사람이 여러 번 칭찬받는 경우
		}
		
		doPraise(1, 0);
		
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < result.length; i++) {
			sb.append(result[i] + " ");
		}
		
		System.out.println(sb);

	}
	
	static void doPraise(int start, int parent) {
		result[start] += result[parent] + credit[start];
		// 해당 칸의 칭찬 수치는 전 칸의 수치 + 현재 칸의 최초 칭찬 수치
	
		for (int next : list[start]) { 
			// 리스트를 한 방향만 추가했기 때문에 추가 조건이 필요없음.
			doPraise(next, start);
		}
	}
}