문제 https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 2차원 좌표의 각각을 정점으로 생각하여 해결하는 벨만-포드 최단 경로 알고리즘 문제. 이번 문제처럼 벨만-포드 문제의 특징은 최단 경로를 구하되 음의 간선(가중치가 마이너스값)이 주어질때 음의 사이클이 구성이 되는지 판정한다. 음의 사이클이 존재하는 경우 상근이는 계속 과거로 돌아갈 수 있으므로 Never를 출력해야 한다. 2차원 좌표계에서 그래프..

문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 다익스트라는 음수 사이클의 존재 여부를 알 수 없으므로 음수 사이클의 존재 여부를 판정할 수 있는 벨만-포드(Bellman-Ford) 최단 경로 알고리즘을 사용하자. 벨만-포드 알고리즘이 음수 사이클의 존재 여부를 알 수 있는 이유는 다음과 같다. 벨만-포드에서는 모든 정점에서 간선으로 연결된 정점으로 이동하는 거리의 완화를 시도한다...

문제 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 단일 시작점 최단경로 알고리즘의 대표 격인 다익스트라는 음수 가중치의 간선이 있는 그래프에서는 정확한 값을 구할 수 없다. 그 이유는 음수 사이클이 반복된다면 우선순위 큐에 음의 최단 거리를 가지는 정점이 무한히 업데이트되며 삽입될 것이다. 따라서 이번 문제와 같이 간선의 가중치로 음수가 주어지는 경우..

문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 다익스트라는 기본적으로 최단 경로 값만 구하기 때문에 동일한 최단 경로가 여러 개가 있더라도 결국 하나의 값만 저장이 된다. 이번 문제는 최단 경로들에 사용된 모든 간선을 사용하지 않고(사실상 제거하고) 최단 경로를 구하는 것이다. 따라서 정점들의 각각에 우선순위 큐를 사용하여 해당 정점에 최소 cost으로 도달..

문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 BFS로도 다익스트라 알고리즘으로도 풀 수 있는 문제. 본인은 다익스트라를 공부 중 이기도 하고 BFS에 비하여 좀 더 효율적이기 때문에 다익스트라로 해결해보자. 일단 처음 문제를 풀때는 두 죄수의 위치에서 다익스트라를 적용하여 해결하려고 했다. 하지만 문제는 두 죄수가 같은 탈출 경로를 이용할 수 있다면 여는 문의 개수를 최소화할 수 있다는 것이다. 하..

문제 https://algospot.com/judge/problem/read/NTHLON algospot.com :: NTHLON 철인 N종 경기 문제 정보 문제 두 나라 A국과 B국은 항상 사이가 좋지 않은데, 국민들 간에 쌓인 감정을 털어버리기 위해 양국의 대표 선수들이 한 명씩 나와 친선 스포츠 경기를 하기로 했다. 채 algospot.com 풀이 종만북 난이도: 상 다익스트라를 이런 식으로도 이용이 가능하다는 것을 알 수 있는 좋은 문제. 그만큼 어렵다... 이번 문제에서 가장 중요한 것은 종목의 진행 순서는 총 코스 소요시간과 상관이 없다는 것이다. 즉, 각각의 종목을 정점으로 설정하여 경로를 만드는 것은 결국 종목의 진행 순서를 만드는 것이므로 이러한 구현이 필요가 없다. 더군다나 이러한 구현..

문제 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 풀이 solved.ac 난이도: Platium 5 다익스트라 최단 경로 알고리즘을 잘 이해해야 풀 수 있는 고난도 문제. 일단 풀이는 다음과 같다. 우선순위 큐를 각 정점마다 하나씩 가지도록 하고(우선순위 큐의 배열을 생성) 해당 정점을 방문할 때마다 그때의 dist(cost, 소요시간)를 우선순위 큐에 push하여 저장한다. 1. 해당 정점의 우선..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 다익스트라 문제 모음 [백준] 파티(1238) - gold 3 [백준] 도로 포장(1162)★ + 다이나믹 - gold 1 [백준] 주유소(13308) + 다이나믹 - gold 1 [알고스팟] 소방차(FIRETRUCKS) - 중 [알고스팟] 철인 N종 경기(NTHLON)★ + 그래프 구현 - 상 [백준] 탈옥(9376)★ 0-1 BFS - Platium 5 [백준] 거의 최단 경로(5719)★ - Platium 5 [백준] K번째 최단경로 찾기(1854)★★ - Platium 5 벨만-포드 문제 ..

문제 https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 algospot.com 풀이 종만북 난이도: 중 처음 문제를 접하면 여러 소방서들에서 불이난 곳으로의 최단 거리를 구해야 된다고 생각하게 됩니다. 하지만 단일 시작점 알고리즘인 다익스트라 최단 경로 알고리즘으로 모든 소방서로부터 불난 곳의 최단 거리를 구하는 것은 시간 초과를 발생시킵니다. 다익스트라 알고리즘의 복잡도는 간선(edge)의 개수를 E라고 할때 O(E logE) 이기..

문제 www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 또다시 다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제. 최단 거리을 저장하는 2차원 배열 dist[city_idx][oil_cost]은 다음의 값을 저장한다. 1번 도시에서 city_idx도시까지의 경로 중 가장 싼 기름 가격이 oil_cost일 때의 최소 비용(최단 거리* 기름 가격) 이를 위해 우선순위 큐에는 3가지 값을 저..