프로그래머스 LV 2 전력망을 둘로 나누기

function solution(n, wires) {
    let answer = Number.MAX_SAFE_INTEGER; // 최소값을 찾기 위함

    // 인덱스는 0부터 전선은 1부터 시작하기 때문에 n + 1
    const graph = Array.from(Array(n + 1), () => []);
    // 인덱스는 노드, 해당 인덱스에 연결된 노드들을 저장
    // 각 전선을 연결된 노드들로 그래프에 추가
    wires.forEach((wire) =>{
      let [from, to] = wire;

      graph[from].push(to);
      graph[to].push(from);
    })
  
    // 출발지점 과 가지않는곳 (연결이 끊긴곳)     
    const dfs = (start,except) => {
        let visited = Array.from(Array(n + 1), () => false);
        let count = 0
        let q = [start]

        visited[start] = true
        // 큐가 비워질때까지
        while(q.length) {
            let n = q.shift()
            graph[n].forEach((i)=>{
                // 연결이 끊기지않고 방문가능하지않은곳
                if(i !== except && visited[i] === false){
                    visited[i] = true
                    q.push(i)
                }
            })
          count++;
        }
        return count
    }
    
    
    wires.forEach((i)=>{
        let [a,b] = i
        console.log(`${i} ___`)
        answer = Math.min(answer,Math.abs(dfs(a,b) - dfs(b,a)))
    })
    return answer;
}

풀이 및 회고

1. wires 배열을 순회하면서 각 노드별로 이동가능한 노드를 저장합니다.

2. dfs() 함수를 작성합니다. 

3. q에 start 노드를 먼저 넣어놓고 이동가능한지 조건을 따지고 이동이 가능하면 이동합니다.

4. count를 빼서 최솟값을 구합니다.