[BOJ] 백준 14267. 회사 문화 1

문제

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

 

 

 

---

풀이

트리에서의 dfs 방법으로 문제를 해결했습니다.

 

 dfs이지만, 배열에서의 누적 합의 매커니즘과 굉장히 비슷한 문제입니다. 

 

누적합은 쉽게 말해, [0,1,1,0,1,1] 과 같은 배열을 nums[i+1] += nums[i] 와 같은 식을 통해 [0,1,2,2,3,4] 과 같은 결과를 도출하는 것입니다. 

 

 이 문제도 마찬가지로, 배열에 값을 입력받고 누적합을 돌리는데 위와 같이 인덱스가 연속된 경우가 아닙니다. 그래서 연속된 인덱스를 dfs로 탐색하며 누적합을 시키는 매커니즘입니다.

 

 

 값을 입력받을 때, list에 사원 번호를 연결시킵니다. 

 

그리고  1번(사장)에서 dfs를 시작해, score 배열을 누적 합을 시켜나갔습니다.

 

아래는 소스코드입니다.

 

 

---

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class B14267_회사문화1 {

    static int N,M;
    static int[] scores;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        scores = new int[N+1];
        list = new ArrayList[N+1];
        for(int i = 0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1;i<N+1;i++){
            int sangsa = sc.nextInt();
            if(sangsa==-1) sangsa = 0;
            list[sangsa].add(i);
        }

        for(int i = 0;i<M;i++){
            int num = sc.nextInt();
            int w = sc.nextInt();
            scores[num] +=w;
        }
        dfs(1);

        for(int i = 1;i<N+1;i++){
            System.out.print(scores[i]+" ");
        }
    }

    static void dfs(int now){
        for(int next:list[now]){
            scores[next] += scores[now];
            dfs(next);
        }
    }
}

 

 

 

 

+ 추가로 아래 처럼 dfs를 각각마다 돌려서 업데이트를 시키면 시간초과가 발생하게 됩니다.

//시간 초과 코드

public class B14267_회사문화1 {

    static int N,M;
    static int[] scores;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        scores = new int[N+1];
        list = new ArrayList[N+1];
        for(int i = 0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1;i<N+1;i++){
            int sangsa = sc.nextInt();
            if(sangsa==-1) sangsa = 0;
            list[sangsa].add(i);
        }

        for(int i = 0;i<M;i++){
            int num = sc.nextInt();
            int w = sc.nextInt();
            scores[num] +=w;
            dfs(num, w);
        }
        for(int i = 1;i<N+1;i++){
            System.out.print(scores[i]+" ");
        }
    }

    static void dfs(int now, int w){
        for(int next:list[now]){
            scores[next] += w;
            dfs(next,w);
        }
    }
}