소개
- 알고리즘 스터디를 참여하며 작성하는 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문제 접근
이 문제는 다음과 같은 순서로 해결할 수 있습니다.
- 그래프 초기화
- 주어진 직원들의 상사 관계를 그래프로 표현합니다.
- DFS 탐색
- DFS를 통해 각 직원이 뉴스를 전달하는데 걸리는 시간을 계산합니다.
- 우선순위 큐 사용
- 직속 부하가 많은 직원부터 뉴스를 전달하여 전체 시간을 최적화합니다.
- 결과 반환
- 모든 직원이 뉴스를 듣는데 걸리는 시간을 반환합니다.
풀이 - 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;
}
}
풀이 설명
- 그래프 초기화
- 주어진 직원들의 상사 관계를 그래프로 표현합니다. graph 배열에 각 직원의 직속 부하를 리스트로 저장합니다.
- DFS 탐색
- DFS를 통해 각 직원이 뉴스를 전달하는데 걸리는 시간을 계산합니다. dfs 함수는 현재 직원 cur부터 시작하여 뉴스를 전달하는데 걸리는 시간을 계산합니다.
- 우선순위 큐 사용
- 각 직원의 직속 부하를 우선순위 큐에 넣어, 직속 부하가 많은 직원부터 뉴스를 전달하여 서브 노드의 최대 시간을 구합니다.
- 결과 반환
- DFS 탐색을 통해 모든 직원이 뉴스를 듣는데 걸리는 시간을 계산하고, 이를 반환합니다.
마무리하며
- 이번 문제를 통해 트리 구조와 DFS 탐색, 우선순위 큐를 활용한 문제 해결 방법을 익힐 수 있었습니다.
- 직속 부하가 많은 직원부터 뉴스를 전달하여 전체 시간을 최적화하는 방법을 학습할 수 있었습니다.
반응형
