Redddy's Devlog

🔈 문제 n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 📝입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 ..

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘은 플로이드와 워셜이 개발한 알고리즘으로 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 데이크스트라 알고리즘과 비슷하게 단계별로 거쳐 가는 노드를 기준으로 최소값을 갱신하지만, 데이크스트라 알고리즘은 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾아서 방문하였다면 이 플로이드 워셜 알고리즘은 아묻따 모든 노드를 탐색한다. 인접 행렬 형태의 2차원 테이블을 만들어 최단 거리 정보를 저장한다. 이전에 한번 한 연산은 다시 반복하지 않는다는 점에서 다이나믹 프로그래밍 유형에 속한다. 이 알고리즘은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하여 갱신해준다. a에서 ..

그래프 : Graph DFS나 BFS는 모두 그래프 순회 알고리즘, 그래프 탐색 알고리즘이다. 그렇다면 그래프에 대해서 자세히 짚고 넘어가자. 우선 알고리즘에서의 그래프는 우리가 흔히 사용했던 막대그래프나 주식그래프 같은 형태가 아니다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 노드와 노드가 간선으로 연결되어 있다면 두 노드는 인접해있다고 한다. 그래프 탐색은 하나의 노드를 시작으로 인접한 노드를 방문하는 것을 말한다. 그래프를 표현하는 방법은 크게 두가지가 있다. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하..