99클럽 코테 스터디 12일차 TIL [DFS]

- 오늘의 학습 키워드 : dfs(깊이 우선 탐색)

[문제 이름 : 뉴스 전하기  (백준 1135, G2) ]

문제 url : https://www.acmicpc.net/problem/11279

 

내가 작성한 코드는 아래와 같다.

import java.util.*;
import java.io.*;
public class Main {
    static ArrayList<Integer>[] tree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 각 직원의 상사 번호 저장
        int[] members = new int[n];
        String[] nums = br.readLine().split(" ");

        for(int i=0; i<nums.length; i++) {
            members[i] = Integer.parseInt(nums[i]);
        }
        System.out.println(solution(n, members));
    }

    static int solution(int n, int[] members) {
        tree = new ArrayList[n+1];
        for(int i=0; i<n; i++) {
            tree[i] = new ArrayList<>();
        }
        int root = -1;
        for(int i=0; i<n; i++) {
            if(members[i] == -1) {
                root = i;
            } else {
                tree[members[i]].add(i);
            }
        }
        return dfs(root);
    }

    static int dfs(int node) {
        // node의 자식 노드들의 뉴스를 전달받는 시간을 저장하는 리스트
        List<Integer> times = new ArrayList<>();

        // 자식 노드 순회
        for(int child : tree[node]) {
            // 자식 노드의 뉴스 전달받는 시간을 리스트에 추가
            times.add(dfs(child));
        }
        System.out.println("node=" + node + "일 때, Times 리스트 : " + times.toString());
        // 자식 노드가 없느느 경우(리프 노드인 경우) 0 리턴
        if(times.isEmpty()) return 0;

        // 자식 노드들이 뉴스 전달받는 시간을 내림차순 정렬
        Collections.sort(times, Collections.reverseOrder());


        // 최대 시간 변수
        int maxTime = 0;
        for(int i=0; i<times.size(); i++) {
            // 각 자신 노드 전달 시간에 i를 더함
            // 이는 해당 노드가 모든 자식 노드에게 뉴스를 전달하는데 걸리는 최대 시간을 계산
            maxTime = Math.max(maxTime, times.get(i)+i+1);
        }
        return maxTime;
    }
}

각 직원은 직속 부하에게 뉴스를 전달하며, 이는 각 노드의 자식 노드들도 재귀적으로 반복된다.

모든 자식 노드가 뉴스를 전달받는 데 걸리는 시간을 고려하여, 부모 노드가 뉴스를 전달받는 데 걸리는 시간을 계산한다.

DFS로 풀이한 이유는, 자식 노드를 깊이 우선으로 탐색하므로 각 노드에서 모든 자식 노드를 먼저 처리한 후, 부모 노드로 돌아와 이후 처리가 가능하기 때문이다.

 

각 노드에서 자식 노드로 뉴스를 전달할 때 걸리는 시간은 자식 노드의 최대 전달 시간 + 자식 노드의 수 이다.

자식 노드가 여러 명일 경우, 뉴스를 전달받는 시간은 자식 노드의 최대 전달 시간과 자식 노드의 수에 따라 달라진다.

 

이때, Math.max를 사용하는 이유는 자식 노드들 사이에서 뉴스를 전달받는 데 걸리는 시간 중 최대 시간을 고려해야 하기 때문이다.

이는 모든 자식 노드가 뉴스를 전달받는 데 걸리는 총 시간을 계산하는 데 중요한 요소다.

각 노드에서 뉴스를 전달받는 데 걸리는 최대 시간을 계산하여 최소 시간을 결정하는 방식이라고 이해하면 된다.

풀이와 위 사진을 이해하며 문제를 보면 좀 더 쉽게 이해할 수 있을 것이다.

풀이 시간 : 1 시간

 

내일은 자기소개서 작성을 마무리할 예정이다.