학습 키워드

• BFS
• DFS

문제 및 해결 방법

문제
2415. 이진 트리의 홀수 레벨 반전

해결 방법

• 이진 트리의 한 레벨을 살펴봐야하기 때문에 BFS를 사용한다.
• 이진 트리 한 level을 살펴보는 방법이다. queue.size()는 현재 살펴볼 level의 노드 수를 나타낸다. currentLevelNodes은 값을 교환할 때 사용하기 위해 필요하다. 현재 노드를 살펴보며 각 노드의 자식 노드를 큐에 집어 넣는다.

   			int size = queue.size();
            List<TreeNode> currentLevelNodes = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currentLevelNodes.add(node);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

• 한 level의 노드를 다 살펴본 후 level이 홀수인지 살펴봐야한다. 홀수라면 val을 교환한다. 마지막으로 level을 증가시켜 다음 레벨로 넘어간다.

전체 코드

public class TreeNode {
      public int val;
      public int level;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
    }
}

class Solution {

     public TreeNode bfs(TreeNode root) {
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<TreeNode> currentLevelNodes = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currentLevelNodes.add(node);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (level % 2 == 1) {
                int left = 0, right = currentLevelNodes.size() - 1;
                while (left < right) {
                    int temp = currentLevelNodes.get(left).val;
                    currentLevelNodes.get(left).val = currentLevelNodes.get(right).val;
                    currentLevelNodes.get(right).val = temp;
                    left++;
                    right--;
                }
            }
            level++;
        }

        return root;
    }
    public TreeNode reverseOddLevels(TreeNode root) {
        bfs(root);
        return root;
    }
}

문제
네트워크

해결 방법

• 방문하지 않는 노드에 dfs를 진행한다.

class Solution {
    
    public static boolean[] visited;
    
    public static void dfs(int start, int[][] computers){
        visited[start] = true;

        for(int i = 0; i<computers[start].length; i++){
                            
            if(start == i) continue;                                

            if(computers[start][i] == 1 && visited[i] == false){
                dfs(i, computers);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        
        visited = new boolean[n];
        int answer = 0;

        for(int i = 0; i<n; i++){
            if(visited[i] == false){
                dfs(i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}