플로이드 와샬

https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 풀이과정 예제 입력으로 플로이드 와샬 알고리즘을 수행한 시간이 입력된다. 그럼에도 불구하고, 플로이드 와샬을 할 때 어느 도시를 거치는 게 더 짧다면 최소 이동시간이 아니므로 이는 불가능한 경우에 해당되며 -1을 출력한다. i에서 j로 가는 경로가 k로 거쳐가는 경우와 같다면 모든 경로를 최소의 도로로 커버해야 하므로 k를 거쳐가는 도로를 선택한다. #include #inclu..

https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, a, b, t, K, city[201]; int num[201][201]; const int INF = 1e9; void floyd() { for (int k = 1; k N >> M; for (int i = 1; i a >> b >> t; num[a][b] = t; } cin >> K; for (int i = 1; i > city[i..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이과정 자신에서 자신으로 갈 수 없으니, i == j 일 때를 제외한 나머지 부분들은 무한대로 초기 설정한다. 그리고 num 배열에 각 정점에서 얻을 수 있는 아이템이 몇 개인지 입력받는다. 플로이드 와샬을 시행했을 때, 결과는 아래 사진처럼 나오게 되는데, 여기서의 숫자들은 각 노드에서 다른 노드를 갈 때 길의 길이가 얼마인지 알려주는 숫자들이다. 수색범위가 m이니까 각 노드에서 갈 때를 비교하여 ..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이과정 일단 각 간선의 가중치를 1로 잡았다. 자신의 키가 몇 번째인지 알 수 있으려면, 자신을 제외한 무한대가 아닌 노드들이 N - 1개여야 한다. num[i][j] = 1이라는 것은 i보다 j가 크다는 뜻이고, num[j][i] = 1이라는 것은 i보다 j가 작다는 뜻이다. 이 두 가지 경우 다 i학생의 기준에서 키의 기준을 알 수 있다. 그러므로 num[i][j] != INF 또는 num[j..

https://www.acmicpc.net/problem/1956  1956번: 운동첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의www.acmicpc.net 풀이과정사이클이 생기는 부분의 최소합을 구하면 되는 문제이다.   i == j일 때는 continue 해주고, arr[i][j] + arr[j][i]일 때의 최솟값을 구하면 된다.   만약 res가 INF일 경우는, 사이클이 되는 곳이 한 곳도 없으므로 -1을 출력해준다. #include #include #include using namespace std;int V..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이과정 예전에 다익스트라 + 플로이드 와샬 문제를 푼 적이 있어서 비슷할 거라고 생각했다. 그러나 생각해야될 것이 많아서 시간이 오래 걸린 문제였다..! 처음에 풀었던 방식은 경유지를 지나면 res배열에 담아주는 방식이다. (2번째 코드) 그러나 이렇게 되면 1행 6열은 1 -> 2 -> 5 -> 6 두개의 경유지를 거치게 되어 첫번째 경유지 2가 아닌, 두번째 경유지인 5를 출력하게 되었다. 최초로 거..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이과정 예전에 풀었던 플로이드 와샬의 백준 키 순서와 비슷한 문제였다. 키 순서 문제 참고하기 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 입력을 받자마자 num[x][y] = 1, ..