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

문제 보러가기

14267번: 회사 문화 1

[문제 풀이]

그래프를 사용하기 위해서 List를 만들어주고 2번부터 N번까지의 상사의 번호에 부하번호를 넣어주었다.

상사의 번호와 칭찬 정도를 총합 칭찬 배열에 넣어주고 List에서 직속 부하 정보를 가져와서

직속 부하의 번호와 칭찬 정도를 총합 칭찬 배열에 넣어주면 완성! 이 아니였다. 시간초과가 나왔다.

 

시간초과를 해결하기 위한 방법으로 입력으로 주어지는 상사의 번호와 칭찬 정도를 배열로서 입력을 추가하고

나중에 배열에 저장된 정보를 바탕으로 총합 칭찬 배열에 넣어주었다.

 

import java.io.*; import java.util.*; class Main {     static List<List<Integer>> nodeList = new ArrayList<>(); //그래프     static int[] numbers; // 상사의 번호와 칭찬 정도를 저장하는 배열     static int[] result; // 총합 칭찬 배열, 각 번호의 직원마다 누적된 칭찬 정도     static int N;     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringBuilder sb = new StringBuilder();         StringTokenizer st = new StringTokenizer(br.readLine());         N = Integer.parseInt(st.nextToken());         int M = Integer.parseInt(st.nextToken());         numbers = new int[N + 1]; //N명의 직원이 있다.         result = new int[N + 1];         for (int i = 0; i <= N; i++) nodeList.add(new ArrayList<>());         st = new StringTokenizer(br.readLine());         for (int i = 1; i <= N; i++) {             int se = Integer.parseInt(st.nextToken());             if (se != -1) { //1번 직원(사장)은 제외되었다.                 nodeList.get(se).add(i);             }         }         for (int i = 0; i < M; i++) {             st = new StringTokenizer(br.readLine());             int node = Integer.parseInt(st.nextToken());             int value = Integer.parseInt(st.nextToken());             numbers[node] += value; //칭찬 정보를 바로 추가하지 않고 누적하고 있다.         }         for (int i = 1; i <= N; i++) {             if (numbers[i] > 0) BFS(i, numbers[i]); // 칭찬 정보를 넣어주는 과정         }         for (int i = 1; i <= N; i++) {             sb.append(result[i]).append(" ");         }         System.out.println(sb);     }     public static void BFS(int node, int value) {         Queue<Integer> queue = new LinkedList<>();         queue.add(node);         while (!queue.isEmpty()) {             int temp = queue.poll();             result[temp] += value; //종합 칭찬 배열에 칭찬 정도를 주입             List<Integer> list = nodeList.get(temp); //현 직원의 부하 정보를 큐에 넣어준다.             for (int A : list) queue.add(A);         }     } }