1. 자료구조 및 알고리즘 9일차 수강하기
- 최소 신장 트리 (MST : Minimum Spanning Tree) 알고리즘
2. 새롭게 알게된 지식
- MST 란?
모든 노드가 연결 되어 있어야함
각각의 노드에서 가중치가 최소가 되는 간선을 선택
- MST 관련 알고리즘
1) Kruskal Algorithm
- 간선(edge) 중심
2) Prim Algorithm
- 정점(vertex) 중심
- 임의의 시작점이 존재
- 인접한 정점 중 가중치가 가장 낮은 정점을 선택
과제 1 : 네트워크 연결 https://www.acmicpc.net/problem/1922
1922번: 네트워크 연결
이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.
www.acmicpc.net
- 접근 :
프림 알고리즘으로 해결
- 코드 구현 :
import sys
from collections import defaultdict
from heapq import heappush, heappop
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
def prim(self, graph : dict, start):
n = len(graph)
visited = set()
heap = []
# 시작할 지점 입력
heappush(heap, (0, start))
result = 0
# 방문한 노드의 갯수가 n개가 되기 전까지 실행
while len(visited) < n :
weight, idx = heappop(heap)
# 이미 방문한 노드라면 continue
if idx in visited:
continue
visited.add(idx)
result += weight
# 현재 노드에 인접한 노드에 대하여 반복 실행
for adj_weight, adj in graph[idx]:
if adj in visited:
continue
heappush(heap, (adj_weight, adj))
return result
def run(self):
num_of_node = int(self.input().rstrip())
num_of_edge = int(self.input().rstrip())
graph = defaultdict(list)
for _ in range(num_of_edge):
idx, adj, weight = map(int, self.input().split(' '))
heappush(graph[idx], (weight, adj))
heappush(graph[adj], (weight, idx))
self.output(str(self.prim(graph, 1)) + '\n')
s = Solution()
s.run()
과제 2 : 세부 https://www.acmicpc.net/problem/13905
13905번: 세부
첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄
www.acmicpc.net
- 접근 :
시작점과 끝점이 주어졌을 때, 갈 수 있는 최장거리를 이동
결과 값으로는 이동한 거리중 최소 값을 반환
- 코드 구현 :
import sys
from collections import defaultdict
from heapq import heappush, heappop
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
def calFunc(self, graph : dict, start, end):
visited = set()
heap = []
# 시작할 지점 입력
heappush(heap, (-1000001, start))
idx = start
res = 1000000
# 도착지점에 도달할때 까지 실행
while heap:
weight, idx = heappop(heap)
# 이미 방문한 노드라면 continue
if idx in visited:
continue
res = min(res, -weight)
visited.add(idx)
# 현재 노드에 인접한 노드에 대하여 반복 실행
for adj_weight, adj in graph[idx]:
if adj in visited:
continue
heappush(heap, (adj_weight, adj))
if idx == end:
return res
return 0
def run(self):
num_of_node, num_of_edge = map(int, self.input().split(' '))
start, end = map(int, self.input().split(' '))
graph = defaultdict(list)
for _ in range(num_of_edge):
temp = self.input().split(' ')
idx = int(temp[0])
adj = int(temp[1])
weight = int(temp[2])
heappush(graph[idx], (-weight, adj))
heappush(graph[adj], (-weight, idx))
self.output(str(self.calFunc(graph, start, end)) + '\n')
s = Solution()
s.run()
'개발일지' 카테고리의 다른 글
심화 과정 11 일차 (0) | 2024.02.23 |
---|---|
심화 과정 10 일차 (1) | 2024.02.23 |
3주차 WIL (0) | 2024.02.18 |
심화 과정 8 일차 (0) | 2024.02.18 |
심화 과정 7 일차 (0) | 2024.02.16 |