서로소 집합
서로소 집합
공통 원소가 없는 두 집합
서로소 집합들로 나누어진 원소들의 테이터를 처리하기 위한 자료구조는 union 연산과 find 연산으로 조작할 수 있다.
union 연산 : 서로 다른 두 원소에 대하여 합집합을 수행하는 것이다. 각각의 루트 노드를 찾아서 그 두 노드 중 더 작은 루트 노드를 가리키도록 하는 방식이다.
find 연산 : 특정 원소가 속한 집합을 찾는 것이다. find_parent 함수를 재귀 호출하여 루트 노드를 찾는 방식이다.
서로소 집합 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def find_parent(parent, x):
# 자기 자신이 parent일 경우에는 자신이 루트 노드라는 것이기 때문에,
# if 문을 건너뛰고 자기 자신을 리턴한다.
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
v, e = map(int, input().split())
parent = [0]*(v+1)
# 처음에는 모두 자기 자신을 루트 노드로 설정함.
for i in range(1,v+1):
parent[i] = i
# 합집합을 수행할 두 노드 조합을 입력받아 union 함수를 실행한다.
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
for i in range(1,v+1):
print(parent[i], end=' ')
서로소 집합을 이용한 사이클 판별
각 간선을 확인하며 find_parent 함수를 통해 두 노드의 루트 노드를 확인하고, 다르면 union 연산을 수행하고, 같으면 cycle이 발생했으므로, 연산을 멈춘다.
위의 알고리즘에서 합집합을 수행하다가 사이클이 발생하면 for 문을 멈추는 알고리즘을 설명해보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
v, e = map(int, input().split())
parent = [0]*(v+1)
for i in range(1,v+1):
parent[i] = i
cycle = False
for i in range(e):
a, b = map(int, input().split())
# 두 루트 노드가 같다는 것은 사이클 발생을 의미함.
if find_parent(parent, a) == find_parent(parent, b)
cycle = True
break
# 사이클이 아니라면 합집합 수행
else:
union_parent(parent, a, b)
print(cycle)
백준 - 마니또
N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와줬는지도 알 수 없다.
그런데 이런 마니또 활동을 하던 중 할 짓이 지지리도 없던 세종이는 여기서 “마니또 체인”이라는 개념을 발견했다! 세종이가 동우에게 선행을 베풀고, 동우가 재혁이에게 선행을 베풀고, 재혁이가 호용이에게 선행을 베풀고… 이렇게 하다 보면 언젠가 누군가는 처음 선행을 베푼 세종이에게 선행을 베풀게 되리라는 것이다. 이렇게 선행을 베푸는 연결 고리가 반드시 생긴다! 이 고리는 그냥 2명일 수도 있고, 아예 N명 모두가 포함될 수도 있다.
우리가 할 일은 N명의 사람들 사이에서 이러한 연결 고리가 몇 개나 발생하는지를 알아내는 것이다. 문제는 여러 개로 이루어져 있다.
입력
각 테스트 케이스의 첫 번째 줄에는 사람의 명수 N이 주어진다(3 <= N <=20). 만약 N = 0이면 입력의 끝을 의미하며 더 이상의 입력은 없다.
각 테스트 케이스의 두 번째 줄부터 N개의 줄에 거쳐 두 사람의 이름이 주어진다. 각 줄에 누가 누구에게 선행을 베푸는지가 주어진다. 첫 번째 이름과 두 번째 이름은 각각 해당 케이스 전체에 걸쳐 중복되지 않으며, 한 줄에 같은 이름이 두 번 등장하지 않는다. 이름의 길이는 10자를 넘지 않는다.
출력
각 테스트 케이스마다, 한 줄에 해당 케이스의 번호(1부터 시작)와 연결 고리의 개수를 공백을 두고 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys
input = sys.stdin.readline
def find_parent(parent,x):
if parent[x] != x:
parent[x] = find_parent(parent,parent[x])
return parent[x]
def union_parent(parent, i):
i.sort() # 사전순으로 나열하여 앞쪽의 원소가 루트 노드
a = i[0]
b = i[1]
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
i = 1
while 1:
cycle = 0
parent = dict()
n = int(input())
if n == 0:
break
for _ in range(n):
a, b = input().split()
if a not in parent:
parent[a] = a
if b not in parent:
parent[b] = b
if find_parent(parent,a) == find_parent(parent,b):
cycle += 1
continue
else:
union_parent(parent,[a,b])
print(i, cycle, end=' ')
i += 1
입력이 문자열로 주어지기 때문에 루트 노드를 설정하는 기준이 필요하다. 이 문제에서는 연결 고리의 개수만 구하면 되기 때문에 방향성은 중요하지 않다. 따라서 입력받은 한 줄을 sort해서 사전순으로 나열하여 사전순으로 앞쪽에 있는 원소를 루트 원소로 설정하였다.
사이클이 발견되면 cycle += 1를 하여서 연결 고리의 개수를 세면되는 간단한 문제다.
백준 - 집합의 표현
초기에 n+1개의 집합 {0}, {1}, {2}, {3}, … , {n} 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 n, m이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.
출력
1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 “YES” 또는 “yes”를, 그렇지 않다면 “NO” 또는 “no”를 한 줄에 하나씩 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
n, m = map(int, input().split())
parent = dict()
for i in range(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):
mode, a, b = map(int, input().split())
if mode:
if find_parent(parent, a) == find_parent(parent, b):
print('yes')
else:
print('no')
else:
union_parent(parent, a, b)
서로조 집합 연산을 입력에 따라 수행하기만 하면 되는 문제..
백준 - 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
입력
첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.
출력
첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import sys
input = sys.stdin.readline
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
n = int(input())
m = int(input())
arr = [[]]
for _ in range(n):
arr.append([0]+list(map(int, input().split())))
parent = dict()
for i in range(1,n+1):
parent[i] = i
for i in range(1,n+1):
for j in range(1,n+1):
if arr[i][j]:
union_parent(parent, i, j)
travel = list(map(int, input().split()))
for i in range(len(travel)-1):
if find_parent(parent, travel[i]) != find_parent(parent, travel[i+1]):
print('NO')
exit(0)
print('YES')
루트 노드가 같지 않다는 것은 그 지역으로 갈 수 있는 경로가 없다는 의미이기 때문에 find_parend를 수행하여 루트 노드가 같으면 YES, 다르면 NO를 출력한다.