풀이 포스팅

[백준 1854번] K번째 최단경로 찾기, C++ 풀이

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 요약 한 정점에서 임의의 정점으로 향하는 K번째 최단경로를 구한다. 1. N개의 도시와 M개의 도로로 이루어진 가중치 방향 그래프가 주어진다. 2. 다익스트라 알고리즘의 아이디어와 우선순위 큐를 활용하여 풀이한다. 3. 기존의 다익스트라 알고리즘에서는 오직 1번째 최단경로만이 중요하므로 한 정점을 방문했을 때의 값이 dist[vertex] ..

[백준 5719번] 거의 최단 경로 / Almost Shortest Path, C++ 풀이

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 요약 정점 S에서 정점 D로 가는 최단경로에 포함되지 않은 도로로만 이루어진 그 다음 최단경로를 구한다. 1. 가중치가 존재하는 단방향 그래프가 주어진다. 2. 다익스트라를 통해 최단경로와 그 경로를 역추적하여 저장한다. https://int-p.tistory.com/13 다익스트라(Dijkstra) 알고리즘과 최단경로 역추적 다익스트라 알고리즘을 활용하여 최단경로를..

[백준 11779번] 최소비용 구하기 2, C++ 풀이

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 요약 정점 S에서 정점 E로 가는 최단경로의 길이와 그 경로를 구한다. 1. A번째 도시와 B번째 도시를 단방향으로 연결하는 버스를 가중치 방향 그래프로 생각할 수 있다. 2. 다익스트라를 통해 최단경로의 길이를 구하고, 그 과정에서 최단경로를 역추적한다. https://int-p.tistory.com/13 다익스트라(Dijkstra) 알고리즘과 최단경로 역추적 다..

[백준 14554번] The Other Way, C++ 풀이

https://www.acmicpc.net/problem/14554 14554번: The Other Way 첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어 www.acmicpc.net 요약 정점 S에서 출발하여 E에 도달하는 서로 다른 최단경로의 개수를 구한다. 1. 정점 S에서 E로 가는 최단경로는 다익스트라를 통해 구할 수 있다. 2. 서로 다른 최단경로의 개수를 구하기 위해서는 다익스트라로 최단거리를 찾는 과정에서 정확히 어떤 경로로 이동하였..

[백준 14611번] 월요병, C++ 풀이

https://www.acmicpc.net/problem/14611 14611번: 월요병 첫 번째 줄에는 지도의 행의 수 N, 열의 수 M이 공백을 사이로 주어진다. (2 ≤ N, M ≤ 300) 다음 N 줄에는 각각 M 개 정수가 주어진다. -2는 벽이 있음을 의미하고, -1은 벽을 세울 수 없는 장소를 의미 www.acmicpc.net 요약 (1,1) 지점에서 (M,N) 지점으로 이어지는 길이 없게끔 벽을 세운다. 1. 미리 정해진 지도의 상태가 주어진다. 이때, 벽이 이미 존재하는 장소, 비용을 지불하고 벽을 세울 수 있는 장소, 벽을 세울 수 있는 장소, 3가지로 분류된다. 2. (1,1) 지점에서 (M,N) 지점으로 이어지는 길이 없게끔 벽을 세우는 아이디어를 떠올려보자. 다음과 같은 좌표 평면..

[백준 17833번] 홍익대학교 지하캠퍼스, C++ 풀이

https://www.acmicpc.net/problem/17833 17833번: 홍익대학교 지하캠퍼스 홍익대학교 서울 캠퍼스의 건물들은 정문부터 후문까지 연결되어 있지만 건물마다 연결되어 있는 층이 제각각이다. 예를 들어 정문인 R동의 3층으로 나오면 K동의 1층이 있고, L동의 8층으로 나 www.acmicpc.net 요약 지하 R층에서 지하 D층으로 이어지는 캠퍼스 모델을 설계한다. 1. 시작 지점 지하 R층과 도착지점 지하 D층이 주어지고, 사용할 수 있는 건물 모델들이 주어진다. 이때, 모델이 최종적으로 위치한 범위가 지하 1층부터 지하 N층을 만족한다면 자유롭게 건물을 배치할 수 있다. 2. 모델을 제작하는데 T의 시간이 걸리고, 건물을 좌우로 반전시켜 배치할 수 있으므로, 가중치가 T인 양방..

[백준 20046번] Road Reconstruction, C++ 풀이

https://www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 요약 (1,1) 지점에서 (N,M) 지점으로 이어지는 경로를 만든다. 1. 미리 정해진 도시의 상태가 주어진다. 이때, 도로가 이미 존재하는 장소, 도로를 건설할 수 있는 장소, 도로를 건설할 수 없는 장소 3가지로 분류된다. 2. 도로가 이미 존재하는 장소는 비용이 0, 도로를 건설할 수 있는 장소는 가중치가 존재, 도로를 건설할 수 없는 ..

[백준 2423번] 전구를 켜라 / Switch the Lamp On, C++ 풀이

https://www.acmicpc.net/problem/2423 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net 요약 (0,0) 지점에서 (M,N) 지점으로 이어지는 회로를 만든다. 1. 미리 정해진 회로의 상태가 주어진다. 이때, 회로는 '/' 방향과 '\' 방향인 두 종류의 선으로 구성된다. 2. 정해진 방향의 회로를 따라 이동할 수도 있고, 이를 90도 회전시켜 방향을 돌린 뒤, 이동할 수 있다. 이때, 정해진 방향의 회로를 따라 이동할 때의 비용을 0, 방향을 회전시킨 뒤 이동하는 비용을 1로 하는 가중치 그래프를 떠올..