[99클럽 코테 스터디] 33일차 TIL DFS/BFS

 

 

오늘의 문제는 LeetCode

 

1530. Number of Good Leaf Nodes Pairs

 

 

문제

 

 

 

문제 설명 

주어진 이진 트리의 루트와 정수 distance를 바탕으로 서로 다른 리프 노드 간의 최단 경로 길이가 distance 이하인 좋은 리프 노드 쌍의 개수를 구하는 문제입니다. 이진 트리에서 리프 노드 쌍들 사이의 경로 길이를 계산한 후, 그 길이가 주어진 distance 이하인 쌍들의 수를 반환해야 합니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 47분이 걸렸습니다.

 

 

 

문제 접근 방식

모든 리프 노드를 찾고 각 리프 노드까지의 경로를 저장합니다. 그런 다음, 모든 리프 노드의 쌍을 비교해 두 리프 노드 간의 경로가 distance 이하인 경우를 확인하고 그 수를 셉니다.

경로의 길이를 계산할 때는 두 리프 노드의 가장 가까운 공통 노드를  찾고, 각 리프 노드에서 가장 가까운 공통 노드까지의 거리 합을 이용합니다. 이러한 방식으로 모든 가능한 리프 노드 쌍을 탐색하고 조건에 맞는 쌍을 찾습니다. 

 

 

 

문제 풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     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 int countPairs(TreeNode root, int distance) {
       
        Map<TreeNode, List<TreeNode>> map = new HashMap<>();
        List<TreeNode> leaves = new ArrayList<>();
        findLeaves(root, new ArrayList<>(), leaves, map);
        int res = 0;
        
        for (int i = 0; i < leaves.size(); i++) {
            
            for (int j = i + 1; j < leaves.size(); j++) {
                
                List<TreeNode> list_i = map.get(leaves.get(i));
                List<TreeNode> list_j = map.get(leaves.get(j));
                
                for (int k = 0; k < Math.min(list_i.size(), list_j.size()); k++) {
                    
                    if (list_i.get(k) != list_j.get(k)) {
                        
                        int dist = list_i.size() - k + list_j.size() - k;
                        
                        if (dist <= distance) {
                            res++;
                        }
                        break;
                    }
                }
            }
        }
        return res;
    }

    private void findLeaves(TreeNode node, List<TreeNode> trail, List<TreeNode> leaves, Map<TreeNode, List<TreeNode>> map) {
        if (node == null) {
            return;
        }
        
        List<TreeNode> tmp = new ArrayList<>(trail);
        tmp.add(node);
        
        if (node.left == null && node.right == null) {
            
            map.put(node, tmp);
            leaves.add(node);
            return;
        }
        
        findLeaves(node.left, tmp, leaves, map);
        findLeaves(node.right, tmp, leaves, map);
    }
}

 

 

DFS를 사용해 리프 노드 탐색하기

트리의 모든 리프 노드를 찾기 위해 DFS를 사용했습니다. DFS는 노드의 자식들을 재귀적으로 탐색하며, 자식 노드가 없는 경우, 즉 리프 노드인 경우에 해당 노드를 추적합니다. 또한, DFS는 트리의 깊은 경로를 우선적으로 탐색하기 때문에 리프 노드까지의 경로를 추적할 수 있습니다. 

 

 

 

백트래킹 알고리즘 

백트래킹이란 DFS 탐색 과정에서 경로를 추적하고, 경로가 필요 없을 때는 이전 상태로 되돌아가면서 다른 경로를 탐색하는 기법입니다.

한 노드를 탐색할 때마다 해당 노드까지의 경로를 기록하고, 리프 노드에 도달하면 그 경로를 사용하여 경로 길이를 계산합니다. 그 다음 현재 경로에서 더 이상 탐색할 노드가 없거나, 다른 경로를 탐색해야 할 경우에는 현재 노드에서 이전 노드로 되돌아가 경로를 수정합니다. 위와 같은 과정을 통해 모든 가능한 리프 노드 쌍의 경로를 효율적으로 탐색할 수 있으며, 불필요한 탐색을 줄이면서 조건에 맞는 쌍을 찾을 수 있습니다.

 

 

 

 

 

 

이렇게 오늘 33일차 TIL을 작성해 보았습니다.