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

문제 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://algospot.com/judge/problem/read/HANOI4 algospot.com :: HANOI4 하노이의 네 탑 문제 정보 문제 하노이의 탑은 세 개의 기둥에 꽂혀 있는 N개의 원반을 가지고 하는 게임입니다. N개의 원반은 크기가 모두 다르며, 게임의 시작 때는 그림과 같이 맨 왼쪽의 기둥 algospot.com 풀이 종만북 난이도: 중 재귀 함수 문제의 대표 격인 하노이 탑 문제에 기둥을 1개 더 추가하여 4개인 상태로 해결하는 문제이다. 이번 문제의 핵심은 각 기둥에 꽂혀있는 원판들의 상태를 어떻게 저장하느냐이다. 단순히 4개의 기둥들이 어떤 원판을 가지는지 stack을 사용하여 표현한다면 4개의 스택(각각의 기둥)을 가지는 구조체로 나타낼 수 있을 것이다. 1 2 ..

문제 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개로 모든 버스를 충분이 정점으로 표현해낼 수 있는 수치이다. 따라서 버스들 ..