문제
문제 정의
- 각 인덱스는 자기의 직원 번호
- 입력으로 주어지는 숫자는 인덱스의 직원의 상사
- 0번 (민식) 직원부터 시작해서 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값 구하기
접근 방법
문제를 확인하고 각 직원들의 관계를 방향 그래프로 그려봤을 때
단방향이며, 사이클이 없고 부모-자식 관계가 형성되는 트리 구조였습니다.
그렇기에 이 문제는 트리로 풀게 되었습니다.
부하 직원이 많은 직원부터 먼저 소식 전하기 (Greedy)
하나의 직원은 여러 부하 직원이 존재할 수 있는데
이 중에 어떤 부하직원을 선택해야 하냐면
그리디하게 해당 부하 직원의 부하들에게
모든 소식을 전하고 오기까지의 시간이 가장 오래 걸리는 부하 직원부터 선택하면 됩니다.
예를 틀어
0번에는 1번, 2번, 5번 부하직원이 있고
1번 부하 직원이 모든 소식을 전하기 까지의 최소 시간이 3이고
2번 부하 직원이 모든 소식을 전하기 까지의 최소 시간이 4이고
5번 부하 직원이 모든 소식을 전하기 까지의 최소 시간이 2인 경우
순서는 2 > 1 > 5가 됩니다.
DFS 수행하기
트리에서 해당 문제를 풀기 위해서는 Top-down 방식으로 재귀 호출을 수행해야 합니다.
상위 문제를 해결하기 위해 DFS를 통해 하위 문제를 해결하는 방식을 사용해서
최하위 문제인 리프 노드부터 문제를 해결하도록 로직을 설계해야 합니다.
DP를 써야할까?
처음에는 DFS를 void로 설계하고 각 dp의 값을
dp[i] = "직원 i가 부하 직원들에게 소식을 모두 돌리기 까지의 최소 시간"으로 정의해서
문제를 해결했었습니다.
하지만 DFS를 구현하다보니
어차피 각 노드는 단 한 번씩만 방문된다는 사실을 알게됐고
DFS의 리턴 타입을 int로 변경한다면 DP 없이 문제를 해결할 수 있으며
메모리나 시간적인 측면에서도 더 효율적일 것이라고 생각해서 리팩토링을 했습니다.
이를 통해 별도의 테이블 참조 오버헤드를 제거하여
실행 시간을 60% 이상(192ms → 68ms) 절감할 수 있었습니다.
코드
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node {
int v;
Node node;
public Node (int v, Node node) {
this.v = v;
this.node = node;
}
}
public class Main {
static StringTokenizer st;
static Node[] graph;
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
graph = new Node[N];
dp = new int[N];
st = new StringTokenizer(br.readLine());
st.nextToken();
for (int i = 1; i < N; i++) {
int v = Integer.parseInt(st.nextToken());
graph[v] = new Node(i, graph[v]);
}
dfs(0);
System.out.println(dp[0]);
}
static void dfs(int v) {
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> dp[o2] - dp[o1]);
for (Node node = graph[v]; node != null; node = node.node) {
int nv = node.v;
dfs(nv);
pq.offer(nv);
}
if (pq.isEmpty()) dp[v] = 0;
else {
int sequence = 0;
while (!pq.isEmpty()) {
int nv = pq.poll();
sequence++;
dp[v] = Math.max(dp[v], dp[nv] + sequence);
}
}
}
}개선된 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node {
int v;
Node node;
public Node (int v, Node node) {
this.v = v;
this.node = node;
}
}
public class Main {
static StringTokenizer st;
static Node[] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
graph = new Node[N];
st = new StringTokenizer(br.readLine());
st.nextToken();
for (int i = 1; i < N; i++) {
int v = Integer.parseInt(st.nextToken());
graph[v] = new Node(i, graph[v]);
}
System.out.println(dfs(0));
}
static int dfs(int v) {
ArrayList<Integer> list = new ArrayList<>();
for (Node node = graph[v]; node != null; node = node.node) {
int nv = node.v;
list.add(dfs(nv));
}
int sequence = 0;
int max = 0;
list.sort(Collections.reverseOrder());
for (int current : list) {
sequence++;
max = Math.max(max, current + sequence);
}
return max;
}
}
