프로그래머스 - 전력망을 둘로 나누기 [못품]

오랜만에 프로그래머스 문제를 풀어봤다.

아직 완벽하지 않아서 감이 있다고는 할 수는 없지만 블록체인 이론 공부만 죽어라 하다보니 못풀었다.

• 사실 알고리즘 공부만 할떄 풀었어도 못풀었을 것이다;; ㅋㅋ

출처 : https://dev-note-97.tistory.com/308?category=884288

일단 이 문제는 처음접해보는 문제여서 방향을 못잡았던 것 같다...ㅠㅠ

문제풀이에 대해서 간략하게 내가 이해한 바를 설명하면

1. 객체를 통해서 서로 연관관계를 만들어냄

2. searchTree를 통해서 들어오는 a,b가 서로 끊어져있다 가정한뒤 DFS를 돌림

3. 한쪽의 경우와 나머지 한쪽의 경우 모두 알아야 하니 둘다 돌리고 그후 중간값을 구하기 위해 뺴줌

4. 절대값으로 그 값을 계속 갱신

이정도 되겠다.

function solution(n, wires) {
  const links = {};
  wires.map((w) => {
    const [a, b] = w;
    if (!links[a]) links[a] = [];
    if (!links[b]) links[b] = [];

    links[a].push(b);
    links[b].push(a);
  });
  console.log(links);

  const searchTree = (root, exc) => {
    let count = 0;
    const queue = [root];
    const visited = [];

    visited[root] = true;

    while (queue.length) {
      const cur = queue.pop();
      links[cur].map((next) => {
        if (next !== exc && !visited[next]) {
          visited[next] = true;
          queue.push(next);
        }
      });
      count++;
    }
    return count;
  };

  let answer = 100;

  wires.map((w) => {
    const [a, b] = w;
    const dif = Math.abs(searchTree(a, b) - searchTree(b, a));

    answer = answer > dif ? dif : answer;
  });
}

links를 서로 연관관계를 보여주는 객체 변수이다.

그후 맨 아래보면 다시 wires를 돌리면서 하나씩 값을 넣어주었다.

searchTree를 보면 dfs를 통해서 탐색을 하고 값을 갱신한다.

개인적으로 이떄까지는 2차원 배열을 만들어서 이러한 문제를 해결하려고 했는데

이런식의 방법이 훨씬간단한것 같다.