[BOJ] 1717: 집합의 표현

이슬비·2023년 1월 24일

Union Find boj 자료구조

Algorithm

목록 보기

64/110

알고리즘 문제 중 처음으로 하루를 넘긴 문제 !

도대체 몇 번을 푼거야 ㅋㅋ...

1. 내 풀이

1. 첫번째 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
n_list = [[i] for i in range(n+1)]

for _ in range(m):
    command, a, b = map(int, input().split())
    if command==0:
        n_list[a].extend(n_list[b])
        n_list[a] = list(set(n_list[a]))
        n_list[b].extend(n_list[a])
        n_list[b] = list(set(n_list[b]))
        for i in n_list[b]:
           n_list[i].extend(n_list[b])
           n_list[i] = list(set(n_list[a])) 
    else:
        if b in n_list[a]:
            print("YES")
        else:
            print("NO")

처음에 시도했던 방법은 2차원 리스트를 만들어서 0 커맨드가 나올 때마다 해당 집합의 원소들의 리스트를 extend 하는 방법이었다.

이 방법의 문제점은,
[[0], [1], [2], [3], [4], [5], [6], [7]]의 리스트가 있을 때 (0, 1, 3)이라는 명령어가 들어오면
[[0], [1, 3], [2], [1, 3], [4], [5], [6], [7]]의 형태가 된다.
그런데 만약 (0, 3, 5)라는 명령어가 들어오면
[[0], [1, 3], [2], [1, 3, 5], [4], [3, 5], [6], [7]]의 형태가 된다.

즉 list[1]에도 5가 포함이 되어야 하는데 그렇지 못한다는 아주 크리티컬한 문제가 생기는 것이다.

2. 두번째 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
n_list = [i for i in range(n+1)]
idx = [i for i in range(n+1)]

for _ in range(m):
    command = sorted(list(map(int, input().split())))
    if command[0]==0:
        n_list[command[2]] = n_list[min(idx[command[1]], n_list[command[1]])]
    else:
        if n_list[command[2]] == n_list[command[1]]:
            print("YES")
        else:
            print("NO")

위에서 조금 달라진 접근이다.

리스트를 만들 때 2개의 리스트를 만들어준다. idx는 실제 값이고, n_list는 그 원소가 현재 어디 집합에 속해있는지를 따져주는 list이다.0 커맨드가 나오면 해당 값의 n_list 값을 동일하게 만들어줄 수 있도록 한다.

여기서 조금만 더 생각했으면 되는데, 아쉽게도 그러질 못했다.

3. 세번째 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
n_list = []

for _ in range(m):
    command, a, b = (map(int, input().split()))
    if command == 0:
        for i in range(len(n_list)):
            if a not in n_list[i] and b not in n_list[i]:
                n_list.append(set(a, b))
    else:
        for i in range(len(n_list)):
            if a in n_list[i]:
                if b in n_list[i]:
                    print("YES")
                else:
                    print("NO")

아예 모든 집합을 다 돌면서 판단하는 방법도 해봤다 ㅎㅂㅎ
물론 시간 초과 뜸 ㅋㅋㅋ

4. 네번째 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
n_list = [i for i in range(n+1)]

def find(x):
    if n_list[x] == x:
        return x
    
    n_list[x] = find(n_list[x])
    return n_list[x]

def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        n_list[b] = a
    else:
        n_list[a] = b

for _ in range(m):
    command, a, b = map(int, input().split())
    if command==0:
        union(a, b)
    else:
        if find(a) == find(b):
            print('yes')
        else:
            print('no')