2학년 동계 모각코 4회차

목표 : 이것이 코딩테스트이다 with python 에서 그래프 이론을 공부해보자.

"서로 다른 개체(혹은 객체)가 연결되어 있다" => 그래프 알고리즘 떠올리자!

그래프 자료구조에서 트리(Tree) 자료구조는 꼭 기억하자!

트리의 특징

• 방향 그래프
• 비순환
• 루트 노드가 존재
• 부모와 자식 관계
• 계층 모델

그래프의 특징

• 방향 혹은 무방향 그래프
• 순환 및 비순환
• 루트 노드가 없음
• 부모와 자식 관계 없음
• 네트워크 모델

서로소 집합

• 공통 원소가 없는 두 집합

union(합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

서로소 집합 알고리즘

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   • A와 B의 루트 노두 A', B'를 각각 찾는다.
   • A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다)
2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

Code

# 기본적인 서로소 집합 알고리즘 소스코드
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return 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

# 노드의 개수와 간선(union 연산)의 개수 입력받기
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)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end ='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

결과

find(찾기) 함수의 최적화 => 경로 압축 기법 : find 함수를 재귀적으로 호출한 뒤에 부모 테이블을 갱신하는 방식

def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

다음과 같이 수정하였더니 부모 테이블이 갱신된 결과를 얻을 수 있었다.

결과

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다.

방향 그래프에서의 사이클 여부는 DFS를 이용해서 판별한다.

서로소 집합을 활용한 사이클 판별 알고리즘

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
   • 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
   • 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

Code

# 특정 원소가 속한 집합을 찾기
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)

if cycle:
    print("사이클이 발생했습니다.")

else:
    print("사이클이 발생하지 않았습니다.")

결과

신장 트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건 => 트리의 조건

크루스칼 알고리즘

• 대표적인 최소 신장 트리 알고리즘 으로 가장 적은 비용으로 모든 노드를 연결할 수 있다.
• 그리디 알고리즘으로 분류된다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   • 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.

최소 신장 트리는 일종의 트리자료구조이므로 간선의 개수 = 노드의 개수 - 1 과 같다는 특징이 있다.

Code

# 크루스칼 알고리즘 소스코드
# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()

for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

결과