[알고리즘] BOJ 1717 집합의 표현

[BOJ] 1717 집합의 표현 문제 바로가기

📍 문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

📍 입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

📍 출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

📍 풀이

• linked list 자료구조를 이용하여 문제를 해결합니다.
• 합집합 연산을 수행할 때는 각 노드의 최상위 부모 노드를 이용하여 연산합니다.
• 두 원소가 같은 집합에 존재하는지 확인하기 위해서 두 원소의 최상위 부모 노드가 같은지 확인합니다.

✍ 코드

from sys import stdin

# 현재 노드의 부모값을 찾는 함수
def FindParent(num):
  while S[num][1]:
    num = S[num][1]
  return num

# a, b 노드의 집합을 더하는 함수
def Union(a,b):
  a = FindParent(a)
  b = FindParent(b)
  if a > b:
    S[b][1] = a
  elif a < b:
    S[a][1] = b

n, m = map(int,stdin.readline().split())
S = []
for i in range(n+1):
  S.append([i,None])

for _ in range(m):
  o, a, b = map(int,stdin.readline().split())
  if o: # 찾기
    if FindParent(a) == FindParent(b):
      print("YES")
    else:
      print("NO")
  else: # 합
    Union(a,b)