prim와 kruskal를 개념과 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해봄으로써
둘의 차이와 알고리즘 동작방식에 대해 확실하게 아는 계기가 되었다.
- 목표 -
[코독하구만 팀] 2020.12.30(수) - 2주차 개인 목표
목표 : prim 알고리즘과 kruskal 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다. 실습은 총 3문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다. 1. prim 알고
codekodo.tistory.com
1. prim 알고리즘
import heapq
def prim(edges, vertices, n):
queue = []
heapq.heappush(queue, [0, vertices[0], vertices[1]]) # 가중치, 시작, 도착
visit = {}
for i in vertices:
visit[i] = False
result = []
sum = 0
while queue:
h = heapq.heappop(queue)
if visit[h[2]] == True: # 도착지점 방문여부 확인
continue
else:
visit[h[2]] = True
sum += h[0] # 가중치 합산
result.append([h[1], h[2], h[0]])
for e in edges[h[2]]: # 다음 도착지점
if (visit[e[0]]) : continue # 다음 도착지점 방문여부 확인
heapq.heappush(queue, [e[1], h[2], e[0]]) # 가중치, 시작, 도착
for e in visit.values(): # 방문하지 않은 노드가 있을 경우(고립된 노드 존재)
if e == False:
sum = 0
break
return sum
def main():
n, m = map(int, input().split())
vertices = input().split()
edges = {}
for i in vertices:
edges[i] = []
for _ in range(m):
u, v, c = input().split() #시작, 도착, 가중치
c = int(c)
edges[u].append([v, c]) #양방향 그래프
edges[v].append([u, c])
print(prim(edges, vertices, n))
if __name__ == "__main__":
main()
2. kruskal 알고리즘
parent = {}
rank = {}
def make_set(v):
parent[v] = v
rank[v] = 0
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
def union(u, v):
root1 = find(u)
root2 = find(v)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
def kruskal(vertices, edges, n):
for u in vertices:
make_set(u)
edges.sort()
sum = 0
for e in edges:
cost, u, v = e # 가중치, 시작, 도착
if find(u) != find(v): # 시작 정점과 도착 정점의 부모가 다를 경우
union(u,v)
sum += cost
return sum
def main():
n, m = map(int, input().split())
vertices = []
edges = []
vertices = input().split()
for _ in range(m):
u, v, c = input().split()
c = int(c)
edges.append((c, u, v)) # 가중치, 시작, 도착
print(kruskal(vertices, edges, n))
if __name__ == "__main__":
main()
3. 가장 중요한 길
parent = {}
rank = {}
def make_set(v):
parent[v] = v
rank[v] = 0
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
def union(u, v):
root1 = find(u)
root2 = find(v)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
def kruskal(vertices, edges, n):
for u in vertices:
make_set(u)
edges.sort()
sum = 0
for e in edges:
cost, u, v = e # 가중치, 시작, 도착
if find(u) != find(v): # 시작 정점과 도착 정점의 부모가 다를 경우
union(u,v)
sum += cost
return sum
def main():
n, m = map(int, input().split())
vertices = []
edges = []
vertices = input().split()
for _ in range(m):
u, v, c = input().split()
c = int(c)
edges.append((c, u, v)) # 가중치, 시작, 도착
standard = kruskal(vertices, edges, n) # 기준이 되는 MST
new_edges = []
result = [] # 중요한 길을 저장할 리스트
for i in edges:
new_edges = edges.copy()
new_edges.remove(i)
if kruskal(vertices, new_edges, n) > standard: # MST 값이 커지면 제거한 엣지가 중요한 길
result.append([i[1], i[2]])
print(len(result))
if __name__ == "__main__":
main()
4. 1197번 최소 스패닝 트리
import heapq
def prim(edges, vertices, n):
queue = []
heapq.heappush(queue, [0, vertices[0], vertices[1]]) # 가중치, 시작, 도착
visit = {}
for i in vertices:
visit[i] = False
result = []
sum = 0
while queue:
h = heapq.heappop(queue)
if visit[h[2]] == True: # 도착지점 방문여부 확인
continue
else:
visit[h[2]] = True
sum += h[0] # 가중치 합산
result.append([h[1], h[2], h[0]])
for e in edges[h[2]]: # 다음 도착지점
if (visit[e[0]]) : continue # 다음 도착지점 방문여부 확인
heapq.heappush(queue, [e[1], h[2], e[0]]) # 가중치, 시작, 도착
for e in visit.values(): # 방문하지 않은 노드가 있을 경우(고립된 노드 존재)
if e == False:
sum = 0
break
return sum
def main():
n, m = map(int, input().split())
vertices = []
for i in range(n):
vertices.append(i+1)
edges = {}
for i in vertices:
edges[i] = []
for _ in range(m):
u, v, c = map(int, input().split()) #시작, 도착, 가중치
edges[u].append([v, c]) #양방향 그래프
edges[v].append([u, c])
print(prim(edges, vertices, n))
if __name__ == "__main__":
main()
- 깃허브 -
github.com/k906506/2020_Winter_Assemble-And-selfcode
k906506/2020_Winter_Assemble-And-selfcode
Contribute to k906506/2020_Winter_Assemble-And-selfcode development by creating an account on GitHub.
github.com
'⛹️ 라이프 > 2020 겨울방학 모각코(개인)' 카테고리의 다른 글
[코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과 (0) | 2021.01.05 |
---|---|
[코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표 (0) | 2021.01.05 |
[코독하구만 팀] 2020.12.30(수) - 2주차 개인 목표 (0) | 2020.12.30 |
[코독하구만 팀] 2020.12.23(수) - 1주차 개인 결과 (0) | 2020.12.23 |
[코독하구만 팀] 2020.12.23(수) - 1주차 개인 목표 (0) | 2020.12.23 |