백준 14267번: 회사 문화 1 [트리][그래프][재귀] - Java

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

14267번: 회사 문화 1

 

 

<첫번째 코드- 시간초과>

칭찬번호 하나씩 받을때마다 계속 재귀함수를 돌았다.

결과적으로 이중포문이 발생해서 시간초과가 났다.

M*N = 100,000*100,000... 폭팔! 예 ~ 

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.List;
import java.util.StringTokenizer;

public class Main {

	public static List<Integer>[] tree;
	public static int[] ans;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		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());
		
		tree = new ArrayList[N+1];
		ans = new int[N+1];
		
		for (int i = 0; i <= N; i++) {
			tree[i] = new ArrayList<Integer>();
		}
		
		//직속부하 list 만들기
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			int boss = Integer.parseInt(st.nextToken());
			if(boss == -1)
				continue;
			
			tree[boss].add(i);
		}
		
		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int emp = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			fun(emp,w);
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 1; i <= N; i++) {
			bw.write(ans[i]+" ");
		}
		bw.flush();
		
	}
	
	public static void fun(int emp, int point) {
		ans[emp]+=point; //내 칭찬점수 + 하기
		
		for (int i = 0; i < tree[emp].size(); i++) {
			int child = tree[emp].get(i);
			fun(child,point);
		}
		
	}

}

 

 

<두 번째 코드 - 성공>

문제의 조건중에 "" 직속 상사의 번호는 자신의 번호보다 작으며, "" 를 활용하였다.

일단 모든 칭찬수치를 각자 그 칭찬대상에게만 저장하고

1부터 N까지 ++하면서 (자기 칭찬수치 + 직속상사의 칭찬수치) 작업을 진행 하였다.

만일 번호가 들쭉날쭉이였다면.. tree를 이용하여 재귀를 써야한다.

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.List;
import java.util.StringTokenizer;

public class Main {

	public static int[] ans, myBoss;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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());
		
		ans = new int[N+1];
		myBoss = new int[N+1];
		

		//직속상사 배열 만들기
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			int boss = Integer.parseInt(st.nextToken());
			
			myBoss[i] = boss;
		}
		
		for (int tc = 0; tc < M; tc++) {
			st = new StringTokenizer(br.readLine());
			int emp = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			ans[emp]+=w;
		}
		
		
		//계산
		for (int i = 1; i <= N ; i++) {
			if(myBoss[i] == -1) //상사가 없음
				continue;
			
			ans[i]+=ans[myBoss[i]];
		}
		
		
		//출력
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 1; i <= N; i++) {
			bw.write(ans[i]+" ");
		}
		bw.flush();
		
	}
	

}