[프로그래머스] 전력망을 둘로 나누기 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

🤔 해결방법

1. wires 배열을 사용해그래프 생성
2. wires 배열의 각 간선을 순서대로 제거하면서 그래프를 두 부분으로 분리
3. 간선을 하나 제거한 후 DFS를 돌며 시작 노드로부터 연결된 모든 노드들의 수 count를 계산 

4. 두 그룹의 노드 수의 차이를 계산하여 차이의 절대값을 answer에 push 후 최솟값 반환

 

 

🔑 풀이

가장 먼저 양방향 그래프를 생성한다.

  // 그래프 생성
    let graph = [...Array(n + 1)].map(() => []);
    for (let i = 0; i < wires.length; i++) {
      let [x, y] = wires[i];
      graph[x].push(y);
      graph[y].push(x);
    }

 

이후 간선들을 순서대로 하나씩 제거하며 dfs를 돌 그래프 separated를 만들어준다.

let separated = JSON.parse(JSON.stringify(graph));
  let [x, y] = wires[i];
  separated[x] = separated[x].filter((e) => e !== y);
  separated[y] = separated[y].filter((e) => e !== x);

 

dfs를 돌면서 연결된 송전탑의 수를 count하고 n - count와의 차이를 answer에 push 후 최소값을 반환하면 된다.

// dfs
  const visited = [];
  function dfs(node) {
    let count = 1; // 연결된 송전탑 수
    visited[node] = true;

    for (const adjacentNode of separated[node]) {
      if (!visited[adjacentNode]) {
        count += dfs(adjacentNode);
      }
    }
    return count;
  }
  let result = dfs(x);
  answer.push(Math.abs(result - (n - result))); // 두 전력망의 송전탑 개수 차이 push

 

최종 코드는 다음과 같다.

function solution(n, wires) {
    let answer = [];
    // 그래프 생성
    let graph = [...Array(n + 1)].map(() => []);
    for (let i = 0; i < wires.length; i++) {
      let [x, y] = wires[i];
      graph[x].push(y);
      graph[y].push(x);
    }

    // 간선을 순서대로 제거
    for (let i = 0; i < wires.length; i++) {
      let separated = JSON.parse(JSON.stringify(graph)); // Deep copy
      let [x, y] = wires[i];
      separated[x] = separated[x].filter((e) => e !== y);
      separated[y] = separated[y].filter((e) => e !== x);

      // dfs
      const visited = [];
      function dfs(node) {
        let count = 1; // 연결된 송전탑 수
        visited[node] = true;

        for (const adjacentNode of separated[node]) {
          if (!visited[adjacentNode]) {
            count += dfs(adjacentNode);
          }
        }
        return count;
      }
      let result = dfs(x);
      answer.push(Math.abs(result - (n - result))); // 두 전력망의 송전탑 개수 차이 push
    }
    return Math.min(...answer);
  }

 

 

📖 배운 점

처음에는 생각없이 다음처럼 그냥 separated에 객체인 graph를 넣어줬었다.

let separated = graph;

그런데 graph는 객체이기에 shallow copy 때문에 에러가 났고 deep copy로 바꿔줘야 했다.

얕은 복사(Shallow Copy)는 참조값이 복사되는 것이라 하나의 데이터를 공유하지만,

깊은 복사(Deep Copy)는 얕은 복사처럼 참조값이 아닌 값만 복사하기에 독립적인 메모리에 따로 할당하여 생성한다.

 

위처럼 얕은 복사로 할 경우 separated에 변동을 주면 graph도 같이 바뀌게 되기 때문에 stringify()와 parse()를 사용해 깊은 복사로 값을 할당해야 한다.

let separated = JSON.parse(JSON.stringify(graph));

  // stringify() 메소드는 객체를 인수로 받으며 받은 객체는 문자열로 치환
  // parse() 메소드는 문자열을 인수로 받으며 받은 문자열은 객체로 치환

깊은 복사를 하는 방법은 stringify()와 parse()를 사용하는 방법 말고도 1. Object.assign()  2. 전개 연산자를 사용하는 방법이 있지만 이 두 가지는 일차원 배열만 깊은 복사가 가능해서 graph처럼 다차원 배열에는 사용할 수 없다.

 

// 얕은 복사
  let a = [1, [2, 3], 4];
  let b = a;
  b[2] = 10;
  console.log(a); // [ 1, [ 2, 3 ], 10 ]
  console.log(b); // [ 1, [ 2, 3 ], 10 ]

  // 깊은 복사
  let a = [1, [2, 3], 4];
  let b = JSON.parse(JSON.stringify(a));
  b[2] = 10;
  console.log(a); // [ 1, [ 2, 3 ], 4 ]
  console.log(b); // [ 1, [ 2, 3 ], 10 ]