Algorithms/Shortest path

https://www.acmicpc.net/problem/1277 1277번: 발전소 설치 첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발 www.acmicpc.net [초기 접근 방법] 1. 1번 발전소에서 N번 발전소까지만 가면 된다. 즉, "1"에서 "N"까지의 최소 경로를 구해야 하므로, 다익스트라 알고리즘을 사용한다. 2. 추가 전선의 길이가 최소가 되게끔 이동한다. 이 때, 두 발전소 사이의 전선 길이가 M을 초과해서는 안된다. 2차원 좌표를 그래프로 표현하면 공간 복잡도가 100억이 나오므로 불..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [초기 접근 방법] 1. 어느 위치에 떨어지는 것이 아이템을 가장 많이 얻을 수 있는가? 2. 모든 노드에서 간선에 대한 수색 범위를 펼쳐서 아이템을 얻는 개수를 구해야 한다. → graph[i]를 중심으로 탐색 범위, 'graph[i][j]

https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net [초기 접근 방법] - M명의 사람들의 출발점이 모두 다르다. → 따라서 플로이드 알고리즘으로 모든 노드 간의 최단거리를 구한다. 1. A 시작점에서 B 지점까지의 최단 경로를 구한다. 2. 위 최단 경로가 C 오픈 시간보다 빠르면 → 파티장에 도착할 수 있다: 길면 → 파티장에 도착할 수 없다. [생각] - 다익스트라나 벨만 포드에 비해, 구현이 직관적이며 간..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net [초기 접근 방법] - 특정 노드에서 출발하여, 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력 - 특정 노드이므로, bfs 탐색과 다익스트라 알고리즘을 사용할 수 있다. [생각] - bfs로는 금방 풀었지만, 다익스트라 알고리즘 복습하는 문제로 좋았다. [코드] 1) bfs # 풀이 시간 : 20분 # 시간복잡도 :..