알고리즘/그래프 알고리즘

플루이드-워셜 알고리즘의 원리를 이용하여 정답을 구해내는 문제이다. 입력값으로 N개의 도시와 미리 계산해놓은 최솟값들을 입력받기 때문에 플루이드-워셜 알고리즘을 역으로 돌리며 인접 행렬을 구해내면 문제를 풀어낼 수 있다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class RoadSum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[][] map = new int[n][n]; int[][] adj = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = ..

플루이드 - 워셜 알고리즘(Floyd - Warshall algorithm) 플루이드-워셜 알고리즘은 최단 경로를 구하는 또 하나의 알고리즘이다. 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 구할 수 있다. 인접 행렬을 이용하여 초기값을 설정한다. 가중치를 포함한 인접 행렬이 다음과 같다고 하자. 이 인접 행렬을 이용해서 다음과 같은 초기값을 만든다. 자신에서부터 자신까지의 거리는 항상 0이며, 직접 연결되어 있지 않은 경우에는 ∞로 초기화 한다. 초기값을 설정한 후에는 n번째 노드부터 중간 노드가 되어, 중간 노드를 거쳐 다른 노드로 갈 수 있는 값들을 업데이트시킨다. n번 반복하면 모든 노드까지의 최단 거리를 알 수 있다. 다음은 Java로 작성한 코드이다. public class Flo..

섬의 크기를 입력받고, map을 입력받은 뒤, 1은 섬, 0 은 바다라 가정한다. 섬에서는 상, 하, 좌, 우, 네방향의 대각선을 포함하여 총 8가지의 이동경로를 가질 수 있다. 하지만, 바다인 경우에는 움직일 수 없다. 즉, 0, 0 위치부터 섬을 찾은 후, 움직일 수 있는 위치까지 모두 방문한 뒤 방문 여부를 기록하면 섬을 중복하여 셀 경우를 피할 수 있고, 방문하지 않은 섬을 새로 발견할 경우 같은 방식으로 진행하면 지도의 모든 섬의 수를 셀 수 있다. 섬을 발견한 경우 깊이 우선 탐색을 이용하여, 갈 수 있는 모든 섬을 방문한 뒤 기록하는 방식으로 문제를 푸는 것이다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.Scanner..

다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘(Dijkstra's algorithm)은 벨만-포드 알고리즘처럼 특정한 노드에서 시작하여 그래프의 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라는 벨만-포드 알고리즘에 비해 좀 더 효율적이기 때문에 그래프가 큰 경우에도 사용할 수 있다는 장점이 있다. 하지만, 이 알고리즘은 음수인 가중치를 가진 간선이 있는 경우에는 사용할 수 없다는 단점이 있다. 다익스트라 알고리즘도 벨만-포드 알고리즘처럼 각 노드까지의 거리를 저장하고 탐색 과정에서 값을 줄여나간다. 각 단계에서는 아직 처리하지 않는 노드 중 거리가 가장 작은 노드를 찾고, 그 노드에서 시작하는 모든 간선을 쭉 살펴보며 노드까지의 거리를 줄일 수 있다면 줄인..

벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘으로 길이가 음수인 사이클을 포함하지 않는 모든 종류의 그래프를 처리할 수 있다. 그래프에 음수 사이클이 있는 경우에는 이를 찾아낼 수도 있다. 이 알고리즘에서는 시작 노드에서 다른 모든 노드까지의 길이를 모두 추적한다. 거리의 초기값은 시작 노드의 경우 0이고 다른 모든 노드의 경우 무한대의 값으로 설정된다. 그리고 이 값을 계속해서 줄여나가는 과정을 더는 줄일 수 있는 값이 없을 때까지 반복한다. 초기 시작 거리가 1인 노드 탐색 거리가 2인 노드 탐색 거리가 3인 노드 탐색 위와 같은 식으로 거리를 줄여나간다. 이후에 거리를 더 줄..

깊이 우선 탐색 (Depth-First Search, DFS) 깊이 우선 탐색은 직관적인 그래프 순회 방식이다. 임의의 시작 노드를 설정하고 간선을 따라 이동해 가며 도달 가능한 모든 노드를 처리한다. 더 이상 갈 수 없는 노드까지 탐색한 후, 이전노드로 돌아가 그래프의 다른 부분을 탐색하기 시작한다. 방문했던 노드를 기록하므로 각 노드는 한 번씩만 처리된다. 1번 노드를 시작으로 정하고, 더 이상 갈 수 없을 때까지 순회한다. 즉 1 -> 2 -> 3 -> 5 순으로 방문한 뒤, 다시 1번 노드로 돌아간다. ( 2번 노드는 이미 방문한 노드이기 때문에 다시 방문하지 않는다. ) 그런 다음 방문하지 않는 노드인 4번 노드를 방문한다. DFS 구현 import java.util.ArrayList; impo..