도시 분할 계획 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, m = map(int, input().split()) parent = [0] * (n+1) for i in range(n+1): parent[i] = i edges = [] r..
분류 전체보기
팀 결성 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, m = map(int, input().split()) parent = [0] * (n+1) for i in range(n+1): parent[i] = i for _ in range(m..
위상 정렬 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 다시 말해, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬 알고리즘은 다음과 같다. 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다. 다만, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 많다. from..
신장 트리(Spanning Tree): 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 크루스칼 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘이라고 한다. 그리고 이 중 대표적인 알고리즘으로 크루스칼 알고리즘(Kruskal Algorithm)이 있다. 구체적인 알고리즘은 다음과 같다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다...
