문제 링크

바로가기

문제 풀이

function solution(n, wires) {
    let answer = Number.MAX_SAFE_INTEGER;
    
    // 그래프 생성
    const graph = [];
    for(let i = 0; i < n + 1; ++i) graph.push(new Array());
    for(const [a, b] of wires) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    const bfs = (rootNum, exceptNum) => {
        const visit = new Array(n + 1).fill(false);
        const queue = [rootNum];
        let cnt = 0;
        visit[rootNum] = true;
        
        while(queue.length > 0) {
            const root = queue.pop();
            for(const num of graph[root]){
                if(visit[num] || num === exceptNum) continue;
                visit[num] = true;
                queue.unshift(num);
            }
            
            cnt++;
        }
        
        return cnt;
    }
    
    for(const [a, b] of wires){
        answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
    }
    
    return answer;
}

import sys

def solution(n, wires):
    answer = sys.maxsize
    graph = [[] for _ in range(n + 1)]
    
    for (a, b) in wires:
        graph[a].append(b)
        graph[b].append(a)
        
    def bfs(startNode, exceptNode):
        cnt = 0
        visit = [False for _ in range(n + 1)]
        queue = [startNode]
        visit[startNode] = True
        
        while queue:
            currentNode = queue.pop()
                
            for node in graph[currentNode]:
                if visit[node] or node == exceptNode:
                    continue
                visit[node] = True
                queue.insert(0, node)
                
            cnt += 1
            
        return cnt
                
    for (a, b) in wires:
        answer = min(answer, abs(bfs(a, b) - bfs(b, a)))
        
    return answer

풀이

어떻게 접근해야할 지 감이 잡히지 않았다.
그나마 다행인 것은 문제를 보고 bfs로 접근해야겠다는 느낌을 받았다.

그래프에서 전력망을 끊으면 해당 간선을 기준으로 두 개의 그래프로 쪼개지게된다.
그러면 그 두 그래프를 bfs로 탐색하면서 몇 개로 구성되어 있는지 검사하면 되겠다고 생각했다.

그래서 먼저 wires를 조금 더 분석하기 쉽게 구조를 수정하였다.
그 다음에 bfs 함수를 만들어서 큐를 이용해 풀었다.
방문한 노드이거나 끊어진 노드면 처리하지 않도록 했다.

마지막으로 모든 간선을 돌면서 두 개의 그래프 갯수의 차이를 계산하였다.

결과

새롭게 배운 점

JS에서 최댓값은 이렇게 쓸 것

Number.MAX_SAFE_INTEGER