graph

플로이드 알고리즘을 이용하여 최단거리를 구해내는 문제이다. 입력받는 값들은 도시의 개수, 버스의 개수, 버스의 시작, 도착, 가중치이다. 최단 거리를 구하기 위해서는 입력받을 때부터 시작 노드와 도착 노드가 동일한 노드 중 가중치가 작은 노드를 택해서 입력받아 저장해야 한다. 따라서 입력받을때 비교하여 인접 행렬을 만들어야 한다. 인접 행렬을 만든 다음에는 직접 연결되어 방문이 가능한 노드는 플로이드 알고리즘을 이용하여 최솟값을 찾아 나가고 직접 연결이 되어 있지 않은 노드는 다른 노드를 거쳐 이동하게 하여야 한다. 하지만, 이 때, 인접 행렬에서 0인 노드로는 접근이 아예 불가능하기 때문에, 이를 고려하여 알고리즘을 작성해야 한다. 다음은 Java로 작성한 코드이다. import java.util.Sc..

플루이드-워셜 알고리즘의 원리를 이용하여 정답을 구해내는 문제이다. 입력값으로 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..

벨만-포드 알고리즘(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..

그래프의 표현 그래프를 표현하는 방법에는 여러 가지가 있다. 그래프의 크기가 어느 정도인지, 그리고 그래프를 어떻게 처리하는지에 따라 알맞은 자료 구조가 결정된다. 인접 리스트 인접 리스트(Adgacency list) 표현법은 그래프의 각 노드 x에 대한 인접 리스트, 즉 x에서 출발하는 간선이 있는 노드의 리스트를 관리한다. 인접 리스트는 그래프를 나타내는 가장 대중적인 방법이다. 인접 리스트를 ArrayList를 이중으로 이용하여 구현할 수있다. import java.util.ArrayList; public class GraphBasic { public static void main(String[] args) { ArrayList adj = new ArrayList(); for(int i = 0 ; ..

그래프(Graph)란? 그래프는 노드(node, 혹은 정점(vertex))와 그들을 잇는 간선(edge)으로 구성되어 있다. 경로(path)는 한 노드에서 그래프의 간선을 지나 다른 노드까지 가는 길을 의미한다. 경로의 길이는 경로에 포함된 간서의 개수이다. 예를 들어 1번 노드에서 5번 노드로 가는 길이가 3인 경로( 1 -> 3 -> 4 -> 5)가 나와 있다. 사이클(Cycle)은 처음 노드와 마지막 노드가 같은 경로를 의미한다. 예를 들어 1 -> 3 -> 4 -> 1로 구성된 사이클이 존재한다. 그래프의 모든 노드 간에 경로가 있는 경우를 연결 그래프(connected graph)라고 한다. 연결 그래프 연결 그래프가 아님 그래프의 연결된 부분을 컴포넌트(component)라고 표현한다. 연결 ..