문제 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에 비하여 좀 더 효율적이기 때문에 다익스트라로 해결해보자. 일단 처음 문제를 풀때는 두 죄수의 위치에서 다익스트라를 적용하여 해결하려고 했다. 하지만 문제는 두 죄수가 같은 탈출 경로를 이용할 수 있다면 여는 문의 개수를 최소화할 수 있다는 것이다. 하..

문제 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. 해당 정점의 우선..

문제 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가지 값을 저..

문제 https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제. 단순히 모든 도로들 중 K개의 도로들을 선택하여 cost를 0으로 만든다면, 모든 조합의 최대 수는 Combination(50000 , 20) 일 것이다. 이는 절대 시간안에 계산해낼 수 있는 수치가 아니다. 따라서 다익스트라를 진행하면서 방문하게 되는 간..

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 다익스트라를 두 번 적용해야 했던 문제. 다익스트라는 최단 경로 알고리즘 중에서 단일 시작점 알고리즘으로 하나의 시작점에서 다른 모든 점까지의 거리를 구한다. 하지만 문제에서는 파티가 진행되는 마을을 도착점으로 하고, 다른 모든 점에서 해당 점을 향해 최단 경로로 이동해야한다. 그렇다면, 반대로 파티 마을을 시작점으로..

문제 https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 풀이를 생각해내는 것은 어렵지 않았지만 구현이 까다로웠던 문제이다. 일단 모든 좌표를 정점으로 만드는 것은 수직선과 수평선이 최대 100,000개이기 때문에 시간 초과는 물론 메모리도 초과해버린다. 하지만 버스의 수는 최대 5000개로 모든 버스를 충분이 정점으로 표현해낼 수 있는 수치이다. 따라서 버스들 ..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 이전 문제인 [백준] 숨바꼭질(1697)의 다음 단계 문제입니다. 이전 문제는 단순히 BFS를 적용하면 풀 수 있었지만 이번에는 최단 시간으로 도달하는 방법 수 까지 구해야합니다. 각 위치의 최단 시간은 수빈이의 시작 위치로 부터 BFS를 하여 도달할 때의 탐색 깊이를 의미합니다. 만약 해당 위치로의 경로가 여..

문제 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 단순히 같은 하이퍼 튜브로 연결된 역들을 양방향 간선으로 이어 문제를 해결하면 시간 초과 또는 메모리 초과가 발생하는 문제였다. 그 이유는 최대 개수인 1000개의 역이 서로 연결된다면 양방향 간선으로 연결 시, 약 1,000,000(=1000^2) 개의 간선이 생성된다. 여기에 최대 1000개의 하이퍼 튜브가 존재한다면..

문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 간단한 BFS 문제. 시작하는 층, S에서 G까지 도달할 수 있는 최소 버튼 push 수를 구해야 한다. 이는 최단 거리를 구하는데 특화된 BFS의 영역이다. 특정 층 floor에서 위(floor + U) 또는 아래(floor - D)층으로 이동할 때 이미 방문했다면 해당 층으로 갈 수 있는 최단 push는 이미 구했으므로 더 이상 계산할 필요가 없다. 하지만..