https://www.acmicpc.net/problem/1389 최단경로 문제다. 그래프가 주어지고 한 점에서 다른 모든 점들까지의 거리가 최소인 점을 찾는 문제다.입력은 연결된 점들의 리스트가 들어온다. 가장 먼저 생각 난 방법은 플로이드 워셜이다.생각은 났는데 공부한 지 좀 지난 개념이라 알고리즘 흐름을 다시 찾아봤다.간단하게 설명하자면, 모든 지점에서 다른 점들까지의 최단 경로를 한 번에 구하는 방법이다.2차원 배열을 이용하고 배열의 각 칸은 i부터 j까지의 최단 거리를 의미한다.3중 반복문(k, i, j)을 통해 min(arr[i][j], arr[i][k] + arr[k][j])를 수행한다.위의 점화식이 의미하는 바는 i부터 j까지 가는 경로 중 k를 거쳐가는 경우의 수를 고려하는 것이다. 플로..
Algorithm/Shortest Path
https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 최단 경로 문제다. 플로이드 워셜을 이용하여 풀었다. 이 문제의 입력은 (시작, 끝, 가중치)가 아닌 배열로 입력이 들어오기 때문에 편했다. 플로이드 워셜을 이용해 모든 지점에서 모든 지점까지의 최단 경로를 구한다. m개의 입력을 맏아 a에서 b까지 걸리는 시간이 c초과와 이하인 경우로 나눠 출력을 한다. #include using namespace std; i..
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 워셜 문제다. 모든 지점에서부터 모든 지점까지의 최단 경로를 구하는 문제다. 문제 이름처럼 플로이드 워셜을 이용한다. 플로이드 워셜은 코테용이 아닌 이론부터 공부를 했다. 플로이드 워셜의 개념은 아래와 같다. dij(k)는 i에서 j까지 가는데 k이하의 수를 거쳐서 지나갔을 때의 최단 경로를 의미한다. 거쳐간다의 의미는 i 와 j를 제외한 노드의 번호다. k == 0 일 때는 아무것도 거..
