이것이 코딩 테스트다 PART2 with python : 그래프이론

j_wisdom_h·2023년 11월 21일
0

CodingTest

목록 보기
56/58

이것이 코딩 테스트다 PART2 with python : 그래프이론

1. 서로소 집합(Disjoint Sets)

수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들이 데이터를 처리하기 위한 자료구조라 할 수 있다. 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다.

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

스택화 큐가 각각 push와 pop연산으로 이루어졌던 것처럼, 서로소 집합 자료구조는 합집합과 찾기 연산으로 구성된다.

서로 집합 자료구조는 union-find자료구조라고 불리기도 한다. 연산의 이름 자체가 합치기와 찾기이기도 하고, 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말과 같기 때문이다.

서로소 집합 자료구조

서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다.

합집합 연산

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

union연산을 효과적으로 수행하기 위해 부모 테이블을 항상 가지고 있어야한다. 또한 루트 노드를 즉시 계산 할 수 없고, 부모 테이블을 계속해서 확인하며 거슬러 올라가야한다. 다시말해 서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야한다.

  • 시간복잡도 : O(VM) ( v: 노드의 개수, M: find 혹은 union 연산개수 )
# 기본적인 서로소 집합 알고리즘 소스

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

# 각 원소가 속한 집합 출력
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함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법이다.
각 노드에 대하여 find함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 된다. 결과적으로 경로 압축 기법을 이용하게 되면 루트 노트에 더욱빠르게 접근할 수 있다는 점에서 기존의 기본적인 알고리즘과 비교했을 때 시간 복잡도가 개선된다.

  • 시간복잡도 : O(V + M(1 + log2-m/v V))
# 특정 원소가 속한 집합 찾기
def find_parent(parent,x):
	# 루트 노드가 이니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    retrun parent[x]
    
# ... 이하 동일 ...

서로소 집합을 활용한 사이클 판별

서로 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다. 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다.

  1. 각 간선을 확인하며 두 노드의 로트 노드를 확인한다.
    a. 루트 노드가 서로 다르다면 두 노드에 대하여 union연산을 수행한다.
    b. 루트 노드가 서로 같다면 사이클이 발생한 것이다.
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.
# 서로소 집합을 활용한 사이클 반별 소스코드

# 특정 원소가 속한 집합 찾기
def find_parent(parent,x):
	# 루트 노드가 이니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    retrun 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("사이클 발생하지 않았다")

2. 신장트리

신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

크루스칼 알고리즘 ( kruskal algorithm )

최소 신장 트리 알고리즘 (가능한 한 최소한의 비용으로 신장 트리를 찾는 알고리즘 )

크루스칼 알고지름을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.

  • 시간 복잡도 : O(ElogE)
  1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
    a. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
    b. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
  3. 모든 간선에 대하여 2번 과정을 반복한다.
# 크루스칼 알고리즘 소스코드

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

edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
	parent[i] = i
    
# 모든 간선에 대한 정보 입력받기
for _ in range(e):
	a,b,cocst = 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)

3. 위상정렬 (Topology Sort)

위상정렬은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적으로 설명하자면, 위상 정렬이란 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.

위상 정렬 알고리즘을 자세히 살펴보기 전에, 먼저 집입차수(indegree)를 알아야 한다. 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다.

  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌때까지 다음의 과정을 반복하낟.
    a. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    b. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

이때 모든 우너소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 사이클이 존재한느경우 사이클에 포함되어 있는 우너소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문이다. 다만, 기본저긍로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많으므로, 여기서는 사이클이 발생하는 경우는 고려하지 않는다.

  • 시간복잡도 : O(V+E)
from collections import deque

# 노그 개수, 간선 개수
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수 0으로 초기화
indegree = [0]  * (v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결리스트 초기화
graph = [[] for i in range(v+1)]

# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
	a,b = map(int, input().split())
    graph[a].append(b) # 정점 A에서 B로 이동가능
    indegree[b] += 1 # 진입차수 1증가
    
# 위상 정렬 함수
def topology_sort():
	result = [] # 알고리즘 수행 결과를 담을 리스트
    q = deque()
    
    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in rnage(1,v+1):
    	if indegree[i] == 0:
        	q.append(i)
    # 큐가 빌 때까지 반복
    while q:
    	now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for i in graph[now]:
        	indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
            	q.append(i)
                
     # 위상 정렬을 수행한 결과 출력
     for i in result:
     	print(i, end =' ')
        
topology_sort()

실전문제 : 팀 결성 (난이도 2)

학생들에게 0 ~ N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른팀으로 구분되어, ㅊㅇ N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.

  1. 팀 합치기 연산은 두 팀을 합치는 연산이다.
  2. 같은 팀 여부 확인 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결괄르 출력하는 프로그램을 작성하시오.

팀합치기 연산은 0 a b, 같은 팀 여부확인은 1 a b 형태로 주어진다.

# 크루스칼 알고리즘 소스코드

# 특정 원소가 속한 집합 찾기
def find_parent(parent,x):
	# 루트 노드가 이니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    retrun 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,m = map(int, input().split())
# 부모 테이블 초기화
parent = [0] * (n+1)

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n+1):
	parent[i] = i
    
for i in range(m):
	oper, a, b = map(int, input().split())
    if oper == 0:
    	union_parent(parent,a,b)
    elif oper ==1:
    	if find_parent(parent,a) == find_parent(parent,b):
        	print('YES')
        else:
        	print('NO')

실전문제 : 도시 분할 계획 (난이도 2)

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 마을 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고있다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 지빙 하나 이상 있어야한다.
일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 각 분리된 마을 안에서도 임의의두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

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

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()
# 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
last = 0

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

실전문제 : 커리큘럼 (난이도 3)

선수 강의가 있는 강의는 선수 강의를 먼저 들어야하만 해당 강의를 들을 수 있다. 총 N개의 강의정보가 주어졌을때 N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.

from collections import deque
import copy

# 노드 개수
v = int(input())
# 모든 노드에 대한 진입차수 0으로 초기화
indegree = [0]  * (v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결리스트 초기화
graph = [[] for i in range(v+1)]
# 각 강의 시간 0츠로 초기화
time = [0] * (v+1)

# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(1,v+1):
	data = list(map(int,input().split()))
    time[i] = data[0]
    for x in data[1:-1]:
    	indegree[i] += 1
        graph[x].append(i)
	
    
# 위상 정렬 함수
def topology_sort():
	result = copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
    q = deque()
    
    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in rnage(1,v+1):
    	if indegree[i] == 0:
        	q.append(i)
    # 큐가 빌 때까지 반복
    while q:
    	now = q.popleft()

        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for i in graph[now]:
        	result[i] = max(result[i],result[now]+time[i])
        	indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
            	q.append(i)
                
     # 위상 정렬을 수행한 결과 출력
     for i in range(1,v+1):
     	print(iresult[i])
        
topology_sort()
profile
j_wisdom_h
뚜잇뚜잇 FE개발자
이전 포스트

이것이 코딩 테스트다 PART2 with python : 최단 경로

다음 포스트

이것이 코딩 테스트다 PART3 with python : 최단거리

0개의 댓글