우선탐색종류

BFS(너비 우선 탐색)

최대한 넓게 이동한 다은 더 이상 갈 수 없을 때 밑으로 내려간다. 보통 힙을 사용하며 두 노드 사이의 최단 경로를 찾고 싶을 때 사용함.

function solution(n, wires) {
    let minDiff = Infinity;

    // 인접 리스트 그래프 생성
    const graph = Array.from({ length: n + 1 }, () => []);

    for (const [v1, v2] of wires) {
        graph[v1].push(v2);
        graph[v2].push(v1);
    }

    function bfs(start) {
        let count = 1;
        const queue = [start];
        const visited = Array(n + 1).fill(false);
        visited[start] = true;

        while (queue.length > 0) {
            const node = queue.shift();

            for (const next of graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.push(next);
                    count++;
                }
            }
        }
        return count;
    }

    for (const [v1, v2] of wires) {
        // 연결 끊기
        graph[v1] = graph[v1].filter(v => v !== v2);
        graph[v2] = graph[v2].filter(v => v !== v1);

        // BFS로 서브트리 크기 계산
        const size1 = bfs(v1);
        const size2 = n - size1;
        minDiff = Math.min(minDiff, Math.abs(size1 - size2));

        // 연결 복구
        graph[v1].push(v2);
        graph[v2].push(v1);
    }

    return minDiff;
}

DFS(깊이 우선 탐색)

최대한 깊이 내려간 뒤 더 이상 깊이 갈 곳이 없는 경우 옆으로 이동

function solution(n, wires) {
    let minDiff = Infinity;

    // 인접 리스트 그래프 생성
    const graph = Array.from({ length: n + 1 }, () => []);

    for (const [v1, v2] of wires) {
        graph[v1].push(v2);
        graph[v2].push(v1);
    }

    // DFS로 연결된 송전탑 개수 찾기
    function dfs(node, visited) {
        let count = 1; // 현재 노드를 포함한 개수
        visited[node] = true;

        for (const next of graph[node]) {
            if (!visited[next]) {
                count += dfs(next, visited);
            }
        }
        return count;
    }

    // 각 전선을 끊어보고 최소 차이 갱신
    for (const [v1, v2] of wires) {
        // 연결 끊기
        graph[v1] = graph[v1].filter(v => v !== v2);
        graph[v2] = graph[v2].filter(v => v !== v1);

        // 송전탑 개수 계산
        const visited = Array(n + 1).fill(false);
        const size1 = dfs(v1, visited);
        const size2 = n - size1;
        minDiff = Math.min(minDiff, Math.abs(size1 - size2));

        // 연결 복구
        graph[v1].push(v2);
        graph[v2].push(v1);
    }

    return minDiff;
}