1. 문제
초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 n, m이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.
출력
1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "
YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.2. 정답 코드
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int,input().split())
parent = [0] * (n + 1)
for i in range(1, n + 1) :
parent[i] = i
def find_parent(parent, x) :
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b) :
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b :
parent[b] = a
else :
parent[a] = b
for _ in range(m) :
order, a, b = map(int,input().split())
if order == 0 :
union_parent(parent, a, b)
else :
if find_parent(parent, a) == find_parent(parent, b) :
print("YES")
else :
print("NO")
3. 생각한 방향 및 설명
합집합, 같은 집합인지 확인?
→ 책에서 공부했던 find, union 알고리즘이 떠올랐다.
크루스칼 알고리즘의 기반이 되는 방법이고 합집합, 해당 원소의 집합을 찾는 알고리즘이다.
- 우선 부모를 자기 자신으로 초기화 한다.
- union : 두 원소가 속한 집합을 합치면 되는데 여기서 find_parent알고리즘이 사용된다.
- find_parent : 루트 노드가 아니라면, 루트 노드를 찾을 때 까지 재귀 호출
- 그 후 루트 노드를 찾게 되면 a, b의 루트 노드를 비교해서 둘 중 작은 크기의 루트 노드로 집합을 합쳐준다.
그래서 각 숫자(n)의 루트는 parent[n]이 되니까
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int,input().split())
parent = [0] * (n + 1)
for i in range(1, n + 1) :
parent[i] = i
def find_parent(parent, x) :
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b) :
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b :
parent[b] = a
else :
parent[a] = b
for _ in range(m) :
order, a, b = map(int,input().split())
if order == 0 :
union_parent(parent, a, b)
else :
if parent[a] == parent[b] :
print("YES")
else :
print("NO")
이렇게 풀면 되겠다 라고 생각을 했었는데 큰 오산이 있었다.
ex)
7 4
0 1 3
0 7 6
0 3 6
1 7 6
#정답 YES
이 반례를 생각하지 못했다.
이렇게 되면 마지막에 1 7 6에서 각각 1과 6이 나오기 때문에 다른 집합에 있다는 착각을 하게 된다. 그 이유는 7의 루트가 수정이 되면서 그 7의 루트인 6의 자식들도 같이 루트가 수정이 되야 하는데 그렇지 않았기 때문이다.
따라서 그냥 parent[a]와 parent[b]를 비교할 것이 아니라 비교할 때 find_parent연산을 한번 더 수행해야 위와 같은 반례를 막을 수 있다.