나그네

1854번: K번째 최단경로 찾기 문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 풀이 다익스트라 알고리즘과 우선순위 큐(최대 힙)를 사용해 풀 수 있는 문제다. 시작 지점이 1로 고정되어 다른 모든 정점까지의 거리를 구하는 문제이므로 다익스트라 알고리즘을 쓸 수 있다. 원래 다익스트라 알고리즘은 최단 거리를 저장하는 dist 배열의 값을 비교해 갱신해 나간다. 하지만 이 문제에서는..

9370번: 미확인 도착지 문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 먼저 가장 큰 접근법은 G-H는 반드시 지나야 하므로 S -> G -> H -> ? 또는 S -> H -> G -> ? 이 최단 경로여야 한다. 따라서 S -> G, S -> H, G -> H, G -> ?, H -> ? 의 최단 거리를 구해야 한다. 즉, 간선 거리는 항상 양수고 몇몇 정점간 거리를 구해야 하므로 다익스트라 알고리즘을 사용했다. 따라서 ..

5719번: 거의 최단 경로 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다. [다익스트라 알고리즘 알아보기] 먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 ..

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 문제 https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 b로 이동했다면 bef[b] = a 형태로 저장하고 다익스트라 알고리즘이 끝난 후 bef[M-1]부터 역으로 돌아가며 경로를 찾아낸다. 비슷한 문제로 [11779 최소비용 구하기 2 문제] | [11779 최소비용 구하기 2 해설]가 있다. 코드 #include using namespace std; #define INF 1000000000 int T, N, M; vector graph[20]; // [정점][다음 정점, 거리] vector dist(20, INF), visited(20, 0)..

2307번: 도로검문 문제 https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 풀이 어느 한 간선을 차단하여 1에서 N까지 최단 경로가 얼마나 거리를 늘릴 수 있는지 구하는 문제다. 다익스트라 알고리즘으로 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 이 문제에서 중요한 것은 최단 경로 이외엔 차단할 필요가 없다. 왜냐하면 어차피 최단 경로로 지나가면 그만이기 때문이다. 그럼 먼저 ..

14284번: 간선 이어가기 2 문제 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 여러 정점 중 두 정점이 연결될 때 간선의 가중치가 최소가 되는 값을 구하는 것이므로 기본적인 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int mai..

4485번: 녹색 옷 입은 애가 젤다지? 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 2차원 배열에서 (0,0)에서 (N-1, N-1)까지 한 칸씩 이동하며 각 칸의 숫자의 합이 최소가 되도록 하는 문제다. 다익스트라 알고리즘을 2차원 배열로 만들어서 풀었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 2차원 배열에서의 BFS처럼 dy, dx 배열을 만들어..

18223번: 민준이와 마산 그리고 건우 문제 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 풀이 최단 경로 중에 민준이가 위치한 정점이 포함되는지 확인하는 문제다. 다익스트라 알고리즘으로 두 정점 간의 최단 경로를 구할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 건우가 위치한 P 정점이 최단 경로 위에 있다면, (시작점부터..

17396번: 백도어 문제 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 0번에서 N-1번까지 가는 최단 경로를 구하는 문제다. 몇 가지 예외만 처리해 주면 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 예외인 경우는 넥서스를 제외한 시야가 밝혀져 있는 정점은 지나갈 수 없다. 따라서 간선을 입력받을 때 해당 정점과 연결..

2211번: 네트워크 복구 문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 1번 정점의 슈퍼컴퓨터에서 모든 정점에 이어야 하므로 최소 시간에 연결이 돼야 하므로 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 문제에서 요구하는 것은 이어야 하는 간선의 수와 그 간선이다. 따라서 -1로 초기화되어 있는 prev 배열을 만..