알고리즘/99Club

99클럽 코테 스터디 12일차 TIL + Java Algorithm

dami97 2024. 8. 3. 00:06
반응형

소개

  • 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
  • TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
  • 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

  • 백준 - 뉴스 전하기 (문제 링크)
  • 다이나믹 프로그래밍
  • 그리디 알고리즘
  • 트리
  • 정렬

문제 설명

민식이는 회사의 매니저입니다. 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 합니다. 민식이의 회사는 트리 구조입니다. 모든 직원은 정확하게 한 명의 직속 상사가 있으며, 자기 자신은 그들 자기 자신의 직접 또는 간접 상사가 아닙니다. 모든 직원은 민식이의 직접 또는 간접적인 부하입니다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 합니다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 합니다. 이 과정은 모든 직원이 뉴스를 들을 때까지 계속됩니다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있으며, 전화는 정확하게 1분 걸립니다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작합니다.

입력

  • 첫째 줄에 직원의 수 N이 주어집니다.
  • 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어집니다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수입니다.
  • N은 50보다 작거나 같은 자연수입니다.

출력

  • 첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력합니다.

입출력 예

예제 입력 1

3
-1 0 0

예제 출력 1

2

예제 입력 2

5
-1 0 0 2 2

예제 출력 2

3

예제 입력 3

5
-1 0 1 2 3

예제 출력 3

4

예제 입력 4

24
-1 0 0 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 12 13 14 16 16 16

예제 출력 4

7

문제 접근

이 문제는 다음과 같은 순서로 해결할 수 있습니다.

  1. 그래프 초기화
    • 주어진 직원들의 상사 관계를 그래프로 표현합니다.
  2. DFS 탐색
    • DFS를 통해 각 직원이 뉴스를 전달하는데 걸리는 시간을 계산합니다.
  3. 우선순위 큐 사용
    • 직속 부하가 많은 직원부터 뉴스를 전달하여 전체 시간을 최적화합니다.
  4. 결과 반환
    • 모든 직원이 뉴스를 듣는데 걸리는 시간을 반환합니다.

 

풀이 - Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

    private static int n;
    private static int[] dp;
    private static ArrayList<Integer>[] graph;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            
            n = Integer.parseInt(br.readLine());
            graph = new ArrayList[n];
            dp = new int[n];
            String[] arr = br.readLine().split(" ");

						// 1. 그래프 초기화
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 1; i < arr.length; i++) {
                graph[Integer.parseInt(arr[i])].add(i);
            }

            // 4. 결과 반환
            System.out.println(dfs(0));

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static int dfs(int cur) {
        int cnt = 0, max = 0;
        
        // 직속 부하가 많은 순서대로 내림차순 정렬
        Queue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);

        // 2. DFS 탐색
        for (Integer next : graph[cur]) {
            dp[next] = dfs(next);
            q.add(dp[next]);
        }

        // 3. 우선순위 큐 사용
        while (!q.isEmpty()) {
            int count = q.poll();
            cnt++;
            max = Math.max(max, count + cnt);
        }

        return max;
    }
}

풀이 설명

  1. 그래프 초기화
    • 주어진 직원들의 상사 관계를 그래프로 표현합니다. graph 배열에 각 직원의 직속 부하를 리스트로 저장합니다.
  2. DFS 탐색
    • DFS를 통해 각 직원이 뉴스를 전달하는데 걸리는 시간을 계산합니다. dfs 함수는 현재 직원 cur부터 시작하여 뉴스를 전달하는데 걸리는 시간을 계산합니다.
  3. 우선순위 큐 사용
    • 각 직원의 직속 부하를 우선순위 큐에 넣어, 직속 부하가 많은 직원부터 뉴스를 전달하여 서브 노드의 최대 시간을 구합니다.
  4. 결과 반환
    • DFS 탐색을 통해 모든 직원이 뉴스를 듣는데 걸리는 시간을 계산하고, 이를 반환합니다.

 

 

마무리하며

  • 이번 문제를 통해 트리 구조와 DFS 탐색, 우선순위 큐를 활용한 문제 해결 방법을 익힐 수 있었습니다.
  • 직속 부하가 많은 직원부터 뉴스를 전달하여 전체 시간을 최적화하는 방법을 학습할 수 있었습니다.

 

 

 

 

 

반응형