[코독하구만 팀] 2020.12.30(수) - 2주차 개인 목표

목표 : prim 알고리즘과 kruskal 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다.

 

실습은 총 3문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다.

 

1. prim 알고리즘

무방향 가중치 그래프가 주어졌을 때 prim 알고리즘을 이용하여 MST를 구하고 그 에지의 합을 출력.

(모든 노드가 연결되지 않아, MST가 없을 경우 0을 출력)

입력 값은 다음과 같이 주어진다.

 

7 12 # N, M
A B C D E F G # 노드의 개수 N 개
A B 7 # 간선의 정보 M 개
C B 8
A D 5
C E 5
D B 9
E B 7
D E 15
E G 9
F G 11
E F 8
F D 6
E D 15

 

2. kruskal 알고리즘

무방향 가중치 그래프가 주어졌을 때 kruskal 알고리즘을 이용하여 MST를 구하고 그 에지의 합을 출력.

(모든 노드가 연결되지 않아도, 구해진 MST 에지의 합을 출력)

입력 값은 다음과 같이 주어진다.

 

7 12 # N, M
A B C D E F G # 노드의 개수 N 개
A B 7 # 간선의 정보 M 개
C B 8
A D 5
C E 5
D B 9
E B 7
D E 15
E G 9
F G 11
E F 8
F D 6
E D 15

 

3. 가장 중요한 길

규태는 네트워크 통신망 관리자다.
기관내 각 건물에 통신 설비가 설치되어 있고, 설비는 각기 다른 응답 속도를 보장한다.
통신에서는 응답 속도가 낮을 수록 좋다.
기관의 통신 장비와 링크 응답 속도가 주어졌을 때,
응답 속도 최소를 보장하기 위한 가장 중요한 길이 몇 개인지 출력하시오.

 

입력 값은 다음과 같이 주어진다.

 

5 7
A B C D E # 노드의 개수 N 개
B A 1  # 간선의 정보 M 개
A E 3
D A 2
B E 6
C B 1
C D 2
E D 3

 

4. 이후 백준에서 prim과 kruskal과 관련된 문제를 풀어본다.

www.acmicpc.net/problem/1197 (1197번 - 최소 스패닝 트리)

1197번: 최소 스패닝 트리