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

- 목표 -

최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습한다.

 

1. 다익스트라

방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오.

 

[입력 값]

6 7

A B C D E F

A B 10

A C 15

B D 12

B F 15

C E 10

D F 1

F E 5

A E

 

[출력 값]

A C 15

C E 10

 

2. 벨만 포드

음의 가중치가 있는 방향 가중치 그래프의 노드와 엣지가 주어졌을 때 방향 가중치 그래프를 그리고, 질의 노드 사이의 최단 거리 엣지 경로를 출력하시오. 만약, 무한 루프가 발생할 경우 Negative Cycle! 이라고 출력하시오.

 

[입력 값]

5 8

A B C D E

A B -1

A C 4

B C 3

B D 2

B E 2

D B 1

D C 5

E D -3

A D

 

[출력 값]
A B -1

B E 2

E D -3

 

3. 경찰서

범죄 발생시 경찰 도착까지 오래 걸리는 문제를 해결하고자 경찰서의 위치를 변경하고자 한다. 마을과 마을간의 거리와 경찰이 쉽게 다다를 수 있는 거리가 입력으로 주어진다. 가능한 많은 마을에 경찰이 쉽게 다다를 수 있는 곳에 경찰서를 이전하고자 한다. 어떤 마을에 경찰서를 설치해야하는지와 몇개의 마을에 쉽게 다다를 수 있는지 출력하시오.

 

[입력 값]
6 7

A B C D E F

A B 10

A C 15

B D 12

B F 15

C E 10

D F 1

F E 5

10

 

[출력 값]
E 4

 

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

백준 1753번 - 최단경로 (www.acmicpc.net/problem/1753)

1753번: 최단경로

백준 1916번 - 최소비용 구하기 (www.acmicpc.net/problem/1916)

1916번: 최소비용 구하기