[백준] 1717번 : 집합의 표현 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1717번: 집합의 표현

 

1. 문제 설명

2. 풀이과정

해당 문제에서 최대 원소의 개수 1,000,000과 질의 개수 100,000이 큰 편이므로 경로 압축이 필요한 전형적인 유니온 파인드 문제이다.

유니온 파인드(union-find)는 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘이다.

union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산

find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 (시간 복잡도가 줄어드는 효과)

1차원 리스트를 이용한다.

 

find 연산의 작동 원리

1. 대상 노드 리스트에 index 값과 value 값이 동일한지 확인
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동
3. 이동 위치의 index 값과 value 값이 같을 때까지 반복 (재귀 함수로 구현)
4. 대표 노드에 도달하면 재위 함수를 빠져나오며 거치는 모든 노드 값을 대표 노드 값으로 변경

슈도코드

1. n(원소 개수), m(질의 개수) 입력받기
2. li(대표 노드 저장 리스트, 처음에는 각 노드가 대표 노드)
3. union 연산 구현 union(a, b):
   1. if (각 a, b의 대표 노드를 찾아 대표 노드가 서로 다르면): 두 원소의 대표 노드끼리 연결
4. find 연산 구현 find(a):
   1. if (a가 해당 집합의 대표 노드이면): a 반환
   2. else: a의 대표 노드 값을 find(li[a]) 값으로 저장 (재귀 함수 형태)
5. check 연산(두 원소가 같은 집합인지 확인) 구현 check(a, b):
   1. 두 노드의 대표 노드가 같은지 결과 반환
6. for m만큼 반복:
   1. op(질의), a, b 입력받기
   2. if (op가 0이면): 집합 합치기 union 연산
   3. else:
      1. if (같은 집합 원소인지 확인하고 같은 집합 원소이면): YES 출력
      2. else: NO 출력

반응형

3. 소스코드

import sys

n, m = map(int, sys.stdin.readline().split())

li = [i for i in range(n + 1)]

def union(a, b):
    if (find(a) != find(b)):
        li[find(b)] = find(a)

def find(a):
    if (li[a] == a):
        return a
    else:
        li[a] = find(li[a])
        return li[a]
    
def check(a, b):
    return (find(a) == find(b))

for _ in range(m):
    op, a, b = map(int, sys.stdin.readline().split())

    if (op == 0):
        union(a, b)
    else:
        if (check(a, b)):
            print('YES')
        else:
            print('NO')