서문

이 문제는 프로그래머스에는 DFS, BFS 문제로 분류가 되어있다. 하지만 나는 이 문제를 읽자마자 Union-Find가 떠올랐고 실제로 많은 사람들이 이를 활용하여 문제를 해결했다.

그래서 해당 문제는 유니온 파인드를 활용해서 풀이를 해보았다. 간만에 써보는 알고리즘이라서 바로 생각이 나지는 않았다. 최대한 떠올리려 노력했으나 일정 부분 이상은 생각이 나질 않아서 기존에 풀었던 코드를 참조해서 해결했다.

그리고 요 며칠 사이에 푸는 문제가 너무 안풀려서 그간 풀이를 올리지 못했다. 다른 문제로 빨리 넘어가서 풀 걸 하는 후회가 남는다. 하루에 한 문제씩 포스팅하는게 목표였는데 너무 빨리 실패한 것 같아서 반성하게 되었다. 앞으로는 최대한 하루에 한 문제씩 풀어서 풀이를 포스팅할 것이다. 너무 안 풀리는 문제는 앞으로 실력을 더 쌓고 나중에 도전해봐야겠다.

소스 코드

function solution(n, computers) {
  let p = new Array(n);

  // 컴퓨터 개수만큼 생성
  for (let i = 0; i < n; i++) {
    make(i);
  }

  for (let i = 0; i < computers.length; i++) {
    for (let j = 0; j < computers[i].length; j++) {
      if (i === j) continue; // 자기 자신은 제외

      // 네트워크로 연결되어 있으면 한 그룹으로 union
      if (computers[i][j] === 1) {
        union(i, j);
      }
    }
  }

  const tmp = []; // 집합의 개수를 세어주기 위해 임시로 만든 배열
  for (let i = 0; i < p.length; i++) {
    const t = find(p[i]); // 최상단의 부모로 업데이트
    // tmp에 포함이 안되어있으면 새로운 집합이므로 추가
    if (!tmp.includes(t)) {
      tmp.push(t);
    }
  }

  // 집합의 개수 출력
  return tmp.length;

  function make(x) {
    p[x] = x;
  }

  function union(x, y) {
    const px = find(x);
    const py = find(y);

    if (px !== py) {
      p[py] = px;
    }
  }

  function find(x) {
    if (p[x] === x) {
      return x;
    } else {
      p[x] = find(p[x]);
      return p[x];
    }
  }
}

풀이

이 문제는 유니온-파인드로 풀었다. 나는 이 알고리즘을 통해 문제를 풀 때 관련 함수들부터 생성한다. 함수들의 이름과 내용은 아래와 같다.

참고로 이 문제에서 사용하는 p array는 parent의 p에서 따온 것이다.

function make

이 함수는 말 그대로 데이터를 생성해주는 역할을 한다. 이 문제에서는 컴퓨터의 개수만큼 생성을 해주었다. 각각의 컴퓨터가 어떤 집합에 속해있는지를 알아야하기 때문이다.
여기서 생성을 할 때, p[x] = x 로 대입을 해준다. 이 때의 의미는 "x의 부모는 x 자기 자신으로 한다" 라는 뜻이다. 본문에서는 컴퓨터의 수만큼 함수를 호출하므로, 각각의 컴퓨터에 대해 같은 동작을 실행하는 것이다.

function union

유니온-파인드의 유니온 함수이다. 이 함수는 두 집합을 하나의 집합으로 합쳐주는 역할을 한다. 매개변수로 두 컴퓨터를 받고 이 둘의 부모를 찾아준다. 만약 두 부모가 같다면 이미 같은 집합에 속한 것이고, 다른 경우에는 서로 다른 집합이므로 합쳐주면 된다. 이 때, 합치는 것은 단순히 한 집합의 부모를 다른 집합의 부모의 자식으로 만들어주면 된다.

function find

유니온-파인드의 파인드 함수이다. 이 함수는 하나의 요소의 부모를 찾아서 반환해주는 역할을 한다. 만약 자기 자신이 부모면 그대로 반환해주고 아니면 자기 자신이 부모가 될 때까지 재귀적으로 계속 호출해준다. 이 행동의 의미는 결국 한 집합의 root 부모를 찾는 것이다. 한 집합마다 집합의 대표인 root 부모가 있는데, 이들은 자기 자신이 부모이다. 그래서 자기 자신이 부모일 경우까지 재귀적으로 계속 호출해주면 최종적으로 한 집합의 대표가 반환되는 것이다.

그런데 유니온-파인드에서는 중간의 부모가 의미가 없다. 결국 어떤 집합인지 알아내는 것이 목적이기 때문에, 중간 부모들을 압축을 해줄 수 있다.
p[x] = find(p[x])의 의미도 x의 부모를 대표 부모로 설정해준다는 의미이다. 이렇게 해줘야 나중에 레벨이 높아졌을 때, 최적화를 해줄 수 있다.

또는 rank를 사용해서 합쳐주는 방법도 있지만 이는 나중에 유니온-파인드 알고리즘을 포스팅할 때 정리해서 올려보도록 하겠다.

알고리즘 풀이

저 위의 함수만 이해하고 짤 줄 알면 실제 문제 풀이는 간단한 편이다. 매개변수로 주어지는 computers 배열을 돌면서 연결되어 있는 경우에 union을 해주면 된다. 그렇게 다 해주면 모든 컴퓨터들이 네트워크(집합)에 속하게 된다. 이렇게 만들어진 p배열을 돌면서 새로운 요소(집합의 대표 부모)를 만나면 tmp 배열에 추가해준다.

그러면 tmp의 길이가 네트워크의 개수가 되므로 tmp.length를 반환해주었다. 여기서 나는 const t = find(p[i]); 을 해주었는데 이는 어떤 요소는 최상단의 부모를 가리지키 않는 경우가 있기 때문에 최상단의 부모를 찾아 반환해주는 작업을 해주었다.

후기

한참 배울 때는 많이 쓰다가 오랜만에 알고리즘을 시작하면서 다시 사용하게 되었는데 이번 기회에 어느정도 정리가 된 것 같다. 다음에 비슷한 유형의 문제를 만나게 되면 이번보다 더 빨리 풀 수 있을 것 같다.