- 목표 -
최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 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번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
백준 1916번 - 최소비용 구하기 (www.acmicpc.net/problem/1916)
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
'⛹️ 라이프 > 2020 겨울방학 모각코(개인)' 카테고리의 다른 글
| [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표 (0) | 2021.01.20 |
|---|---|
| [코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과 (0) | 2021.01.13 |
| [코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표 (0) | 2021.01.13 |
| [코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과 (0) | 2021.01.05 |
| [코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표 (0) | 2021.01.05 |
| [코독하구만 팀] 2020.12.30(수) - 2주차 개인 결과 (0) | 2020.12.30 |