[Java 알고리즘] 트리노드 배열로 반환하기(BFS, Queue), 너비우선탐색 문제풀이

문제 설명

 

클래스 TreeNode가 다음과 같이 있을때

class TreeNode {
  int val;
  TreeNode left, right;

	public TreeNode(int x) {
	this.val = x;
	}
}

다음과 같은 트리노드를 구현한 매개변수로 TreeNode 인스턴스를 받고 다음의 배열로 표현되도록 하시오.

 

결과 : [[33], [22, 44], [3, 26, 77], [55]]

 

나의 풀이

public List<List<Integer>> solution(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if(root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(list);
        }
        return result;
    }

일단 노드의 root격이 되는 TreeNode 인스턴스를 받으면 null 체크를 해줍니다. 값이 비면 빈 리스트를 리턴해야하기때문입니다.

 

루트노드를 큐에 담고 while문으로 반복작업을 정의합니다. Queue는 루트에서부터 1개씩 내려가면서 자식노드를 담을 것입니다. 그 작업을 for문이 하는 것입니다. For 문에서 루트를 먼저 예로 들면

 

Queue root out -> queue size 0 -> root left, right check -> left, right is not null -> queue 사이즈 증가. -> for문 종료 -> 리스트 담기

이런 패턴으로 반복되게 됩니다. 

 

For문이 끝나는 것은 루트노드의 자식노드를 queue에 담아 다음 for문의 size를 주는 역할을 하게되고, 각각의 자식노드는 다음 while 반복문에서 list에 담길 것이고 queue에는 그 자식노드의 자식노드들을 담아주게 됩니다.

 

이러한 문제의 유형을 BFS(너비우선탐색)이라고 합니다. 

 

비슷한 유형의 문제로 DFS(깊이우선탐색)이 있는데 두 유형중 어떤 것인지에 따라 Stack과 Queue중 어느 것을 이용해야하는지 결정된다고 합니다.

 

저는 앞으로 bfs, dfs에 대한 문제를 많이 풀어보려고 합니다.

 

카테고리 알고리즘으로 가셔서 어떤 문제들이 있는지 확인해보시고 저랑 같이 알고리즘 문제풀이 함께해보았으면 앞으로의 개발자로서의 능력향상에 도움이 되지 않을까 합니다.

 

감사합니다.