백준 14267 회사 문화 1 [JAVA]

solved.ac = 골드 4

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

14267번: 회사 문화 1

 

---

1. 접근

 

먼저 문제를 살펴보겠습니다.

문제 속 지문을 살펴보면 요구사항은 두 가지로 보입니다.

 

특정 직원을 칭찬하면 칭찬받은 직원의 부하 직원들도 같이 칭찬받는다.

칭찬에는 수치가 있으며 모든 칭찬이 끝나면 모든 직원들에 대해 누적 칭찬 치를 출력한다.

 

예제 입력을 예시로 각 직원을 노드로, 상하 관계를 부모 자식 관계로 나타낸 트리로 보면 다음과 같습니다.

그림을 보며 위 요구사항을 다시 정리하면

 

특정 직원을 칭찬하면 칭찬받은 직원의 부하 직원들도 같이 칭찬받는다.

=> 특정 노드에 값을 더하면 자식 노드의 값도 더해진다!

칭찬에는 수치가 있으며 모든 칭찬이 끝나면 모든 직원들에 대해 누적 칭찬치를 출력한다.

=> 단순 이동거리가 아닌 특정 숫자가 주어지며 모든 노드의 값을 출력해야 한다!

 

즉, 모든 노드의 칭찬받은 정도를 출력해야 하니 당연히 모든 노드를 다 확인해야 하는데

입력 제한사항을 살펴보면 칭찬의 정도는 최대 1,000, 칭찬의 회수 및 직원의 수는 최대 100,000입니다.

 

즉, 입력의 최댓값은 칭찬의 수치 최대값 * 직원 최대의 수 = 1,000 * 100,000 = 100,000,000로 Integer를 사용해도 되며

매 칭찬마다 자식 노드를 탐색하면 최악의 경우 m²으로 약 100억인데 이는 시간제한 2초 안에 풀 수 없습니다.

따라서 DP를 이용해 최초 입력값에서 각 노드에 칭찬 값을 세팅한 후 본인의 칭찬 수치를 자식의 칭찬 수치에 더하는 방법으로 한 번의 탐색으로 끝내야 합니다.

캬! 훈훈하니 보기 좋다!

 

이후 카운트한 배열을 1번 직원부터 순서대로 출력하면 정답입니다.

 

---

2. 풀이

 

변수 세팅

static int N, M;
static ArrayList<Integer>[] tree;
static int[] cnt;
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    tree = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) tree[i] = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
        int x = Integer.parseInt(st.nextToken());
        if (x == -1) continue;
        tree[x].add(i); // 밑으로만 뻗어나가니 반대의 경우는 add하지 않는다.
    }

    cnt = new int[N + 1];
    for (int i = 1; i <= M; i++) {
        st = new StringTokenizer(br.readLine());
        // x = 칭찬받은 번호 , y = 칭찬 수치
        int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
        cnt[x] += y;
    }

    solution();
}

 

탐색 및 정답 출력

static void solution() {
    DFS(1);
    for (int i = 1; i <= N; i++) sb.append(cnt[i]).append(' ');
    System.out.println(sb.toString());
}

 

탐색 

static void DFS(int x) {
    for (int y : tree[x]) {
        cnt[y] += cnt[x]; // 부하 칭찬 누적치에 본인 칭찬 누적치를 더한다!
        DFS(y);
    }
}

 

---

3. 전체 코드