[Baekjoon] 14267_회사 문화 1

Gold IV

문제(출처: https://www.acmicpc.net/problem/14267)

---

< 회사 문화 1 >

 

문제 풀이 & 생각

 

직속 상사의 번호를 입력받으므로 이 정보를 이용해서 각 직원의 직속 부하를 저장해 둔다.

 

처음에는 직속 부하 정보를 저장해 둔 것을 이용해서 답을 구했지만 시간 초과가 발생했다.

그 이유는 칭찬을 받을 때마다 dfs 함수를 호출해서 시간 초과가 발생했던 것이다.

이것을 해결하기 위해 칭찬을 다 저장한 후 dfs 함수를 한 번 호출하여 구했더니 통과할 수 있었다.

 

 시간초과 코드(Java)

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

public class Main { // 회사 문화 1
	static int sup[];
	static long answer[];
	static ArrayList<ArrayList<Integer>> sub;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		sup = new int[n + 1];
		answer = new long[n + 1];
		sub = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			sub.add(new ArrayList<>());
		}

		st = new StringTokenizer(bf.readLine());
		for (int i = 1; i <= n; i++) {
			sup[i] = Integer.parseInt(st.nextToken());
			if (sup[i] > -1)
				sub.get(sup[i]).add(i);
		}

		for (int j = 0; j < m; j++) {
			st = new StringTokenizer(bf.readLine());
			int i = Integer.parseInt(st.nextToken()); // 직원 번호
			int w = Integer.parseInt(st.nextToken()); // 칭찬의 수치
			dfs(i, w);
		}

		for (int i = 1; i <= n; i++) {
			bw.write(answer[i] + " ");
		}
		bw.flush();
	}

	private static void dfs(int idx, int w) {
		answer[idx] += w;
		for (int i = 0; i < sub.get(idx).size(); i++) {
			dfs(sub.get(idx).get(i), w);
		}
	}
}

 

 my solution (Java)

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

public class _14267_ { // 회사 문화 1
	static int sup[], answer[];
	static boolean visited[];
	static ArrayList<ArrayList<Integer>> sub;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		sup = new int[n + 1];
		answer = new int[n + 1];
		visited = new boolean[n + 1];
		sub = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			sub.add(new ArrayList<>());
		}

		st = new StringTokenizer(bf.readLine());
		for (int i = 1; i <= n; i++) {
			sup[i] = Integer.parseInt(st.nextToken());
			if (sup[i] > -1)
				sub.get(sup[i]).add(i);
		}

		for (int j = 0; j < m; j++) {
			st = new StringTokenizer(bf.readLine());
			int i = Integer.parseInt(st.nextToken()); // 직원 번호
			int w = Integer.parseInt(st.nextToken()); // 칭찬의 수치
			answer[i] += w;
		}
		
		for(int i=1; i<=n; i++) {
			if(answer[i]>0 && !visited[i]) {
				visited[i]=true;
				dfs(i);
			}
		}

		for (int i = 1; i <= n; i++) {
			bw.write(answer[i] + " ");
		}
		bw.flush();
	}

	private static void dfs(int idx) {
		for (int i = 0; i < sub.get(idx).size(); i++) {
			int next=sub.get(idx).get(i);
			answer[next]+=answer[idx];
			visited[next]=true;
			dfs(next);
		}
	}
}

 

Main

- 회사 직원의 수 (n), 최초의 칭찬의 횟수 (m) 입력

- sup : 직속 상사의 번호 저장
  answer : 칭찬받은 정도 저장
  visited: 방문 여부

  sub : 직속 부하의 번호 저장

- 직속 상사의 번호를 입력받으면서 직속 하사의 번호를 저장

- 직원 번호(i), 칭찬의 수치(w) 입력 후 answer에 칭찬 수치 저장

- 칭찬을 받았지만 아직 직속 부하에게 전달을 안 했다면 dfs 함수 호출

- answer 출력

 

dfs

- 직속 부하가 있다면 직속 부하에게 칭찬 전달 후 dfs 호출

---

---