심화 과정 9 일차

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번: 네트워크 연결

 

 - 접근 : 

 

 프림 알고리즘으로 해결

 

 - 코드 구현 : 

 

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번: 세부

 

 - 접근 : 

시작점과 끝점이 주어졌을 때, 갈 수 있는 최장거리를 이동

결과 값으로는 이동한 거리중 최소 값을 반환

 

 - 코드 구현 : 

 

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()