알고리즘 | 집합 찾기 Union - Find Set 알고리즘

dev_hee·2021년 10월 8일
1

알고리즘

목록 보기
5/7
post-thumbnail

합집합 찾기(Union and Find Set) 알고리즘

많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다.

두개의 연산을 수행한다.

Find

어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다.

어떤 원소가 속한 집합을 대표하는 원소를 반환하는데, 

이를 위해 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.

Union

두 개의 집합을 하나의 집합으로 합친다.

예제 문제

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 철수네 반 학생은 N명이다.
철수는 각학생들의 친구관계를 알고 싶다.
모든 학생은 1부터 N까지 번호가 부여되어 있고, 철수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.
학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.
두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

✏️입력설명
매개변수 n에 반 학생수인 자연수 N(1<=N<=1,000)이 주어집니다.
매개변수 nums에 M(1<=M<=3,000)개의 숫자쌍이 주어집니다.
매개변수 s1, s2에 두 학생이 친구인지 확인해야 하는 학생번호가 주어집니다.

✏️출력설명
“YES"또는 "NO"를 반환합니다.

📌매개변수 형식
19, [[1, 2], [2, 3], [3, 4], [1, 5], [6, 7], [7, 8], [8, 9]], 3, 8

📌반환값 형식
NO

문제에서 매개변수 중 nums 숫자쌍을 그래프로 표현하면 다음과 같다.

위와 같은 연결을 처리하기 위해서는 Union과정을 거쳐야한다.

Union 과정에는 Find가 포함되어있다.

먼저 0~9 번 친구들이 제 각각의 집합을 가지고 있다고 초기값을 unf배열에 저장한다.

즉, unf는 해당 원소가 포함되어 있는 집합의 대표 원소를 의미한다.

unf 배열은 다음과 같다.

이후 nums에 들어있는 연결 쌍들을 Union 과정으로 연결 시켜주면 된다.

Union은 다음과 같이 구성된다.

Union 과정

  // 원소 a, b를 같은 집합으로 연결한다. 즉 대표 원소를 동일하게 설정한다.
  function Union(a, b) {
    let fa = Find(a); // a의 대표 원소를 찾는다
    let fb = Find(b); // b의 대표 원소를 찾는다
    if (fa !== fb) {
      // 대표 원소가 다르다면, 대표 원소를 동일하게 바꾼다.
      unf[fa] = unf[fb];
    }
  }

그렇다면 대표 원소를 찾는 Find 과정 또한 설정해야한다.

해당 원소가 포함되어 있는 집합의 대표 원소는 unf배열에 들어있는 값이다. 

따라서 Find는 다음과 같이 구성된다.

Find 과정

  function Find(x) {
    // 자기 자신이 대표 원소인 경우, 최종 대표 원소를 찾은 것.
    if (x === unf[x]) return x;
    // 자기 자신이 대표 원소가 아니면, 최종 대표 원소를 찾아가야함.
    else return (unf[x] = Find(unf[x])); // 대표 원소를 갱신
  }

왜 unf에 들어있는 값이 대표값으로 바로 결정되는 것이 아니고,

Find 함수를 재귀 호출하여 찾아야 하는가?

그 이유는 Union 과정에서 설정한 대표 원소가 그 이후에 또 Union과정을 거쳤을 때,

이전에 설정한 대표원소 또한 수정해 주어야 하는데 그러지 않았기 때문이다.

그렇게 하지 않아도 되는 이유는 Find 과정에서 최종 대표 원소를 자기 자신이 대표 원소인 경우로 알 수 있기 때문에,

자기 자신이 대표 원소가 아니면 그 때 변경된 대표 원소로 수정해주면 되기 때문이다.

그런 과정을 거치면 아래와 같다.

1. 처음

처음에는 각각의 원소가 각각의 집합을 가진다.

2. [1, 2]

1과 2가 같은 집합이여야 한다. 따라서 Union 함수로 idx = 1과 idx = 2의 대표 원소를 2로 통일한다.

3. [2, 3]

2, 3이 같은 집합이여야 한다. 따라서 Union 함수로 idx = 2과 idx = 3의 대표 원소를 3으로 통일한다.

4. [3, 4]

3, 4이 같은 집합이여야 한다. 따라서 Union 함수로 idx = 3과 idx = 4의 대표 원소를 4로 통일한다.

5. [1, 5]

1, 5이 같은 집합이여야 한다. 

하지만 unf[1] = 2로 자기 자신이 대표 원소가 아니다.

따라서 대표 원소를 찾아서 Find를 해주게 되면, 결국 unf[4] = 4에서 대표 원소를 찾게 되고,

따라서 4와 연결되어 있던 1, 2, 3의 대표원소는 전부 4로 바뀌게 된다.

이후 4, 5를 같은 집합으로 설정하기 위해 Union 함수로 idx = 4과 idx = 5의 대표 원소를 5로 통일한다.

6. [6, 7]

6, 7이 같은 집합이여야 한다. 따라서 Union 함수로 idx = 6과 idx = 7의 대표 원소를 7로 통일한다.

7. [7, 8]

7, 8이 같은 집합이여야 한다. 따라서 Union 함수로 idx = 7과 idx = 8의 대표 원소를 8로 통일한다.

8. [8, 9]

8, 9이 같은 집합이여야 한다. 따라서 Union 함수로 idx = 8과 idx = 9의 대표 원소를 9로 통일한다.

마지막

이후 입력받은 s1, s2이 같은 집합에 있는지 Find로 확인해주면 된다.

만약 s1이나 s2이 최종 대표 원소가 아니라면, Find에서 재귀를 통해 최종 대표 원소를 찾아서 반환한다.

위와 같은 알고리즘을 자바스크립트 코드로 구현하면 다음과 같다.

  function solution(n, nums, s1, s2) {
    let answer = "YES";
    let unf = Array.from({ length: n + 1 }, (v, i) => i);

    function Find(x) {
      if (x === unf[x]) return x;
      else return (unf[x] = Find(unf[x])); // 대표 원소를 찾아서 갱신해줌
    }
    function Union(x, y) {
      let fa = Find(x);
      let fb = Find(y);

      if (fa !== fb) {
        unf[fa] = unf[fb];
      }
    }

    for (let [a, b] of nums) {
      Union(a, b);
    }

    if (Find(s1) !== Find(s2)) answer = "NO";

    return answer;
  }
  console.log(
    solution(
      9,
      [
        [1, 2],
        [2, 3],
        [3, 4],
        [1, 5],
        [6, 7],
        [7, 8],
        [8, 9],
      ],
      3,
      8
    )
  ); // NO
  console.log(
    solution(
      9,
      [
        [1, 2],
        [2, 3],
        [3, 4],
        [1, 5],
        [6, 7],
        [7, 8],
        [8, 9],
      ],
      3,
      2
    )
  ); // YES

덧으로 DFS

참고로 해당 예제는 DFS로도 풀 수 있다. 코드는 아래와 같다.

 function solution(n, nums, s1, s2) {
    let answer = "NO";
    let graph = Array.from({ length: n + 1 }, () => Array());
    let ch = Array.from(n + 1).fill(0);
    for (let [a, b] of nums) {
      graph[a].push(a);
      graph[b].push(a);
    }

    function DFS(v) {
      if (v === s2) answer = "YES";
      if (ch[v] === 1) return;
      for (let x of graph[v]) {
        ch[v] = 1;
        DFS(x);
      }
    }
    DFS(s1);
    return answer;
  }

참고
https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

profile
🎨그림을 좋아하는 FE 개발자👩🏻‍💻

0개의 댓글