559. Maximum Depth of N-ary Tree

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

팀 알고리즘 레포지토리 주소

ROUTINE-STUDY/Algorithm

문제 출처

Maximum Depth of N-ary Tree - LeetCode

[문제 설명]

높이의 깊이를 구하시오. 예제에서는 5,6이 최대 깊이므로 3이 됩니다.

[처음 생각한 접근 방법]

기본적인 BFS 방식으로 접근하면 될 거 같았습니다.

계층만큼 for문을 반복해서 끝나면 다음 계층으로 가는 식으로 하는 걸로 했습니다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxDepth(Node root) {
        //BFS를 위해 Queue이용.
        Queue<Node> q = new LinkedList<>();
        //깊이를 저장할 변수를 선언.
        int depth = 0;
        //만약 노드가 하나도 없으면 0층을 반환.
        if (root == null) return 0;
        //제일 최상단 노드를 넣어줌.
        q.offer(root);

        //Queue가 빌 때까지 반복(모든 계층 탐색)
        while (!q.isEmpty()) {
            //일단 Queue에 요소가 있으므로 계층이 있음
            //-> depth를 증가.
            depth++;
            //계층의 크기를 구해줌.
            int size = q.size();

            //계층의 크기만큼 반복.
            //위의 예제로 치면,
            //1
            //3,2,4
            //5,6
            while (size-- > 0) {
                Node node = q.poll();
                //계층에 자식 요소들을 넣어줌.
                //다음층을 위해서.
                for (Node child : node.children) {
                    q.offer(child);
                }
            }
        }

        //깊이를 반환.
        return depth;
    }
}