SY DevLog

플로이드 워셜 알고리즘 그래프에서 모든 정점들 간의 최단거리를 구하는 알고리즘 다익스트라 알고리즘 비교 다익스트라 알고리즘은 하나의 시작 정점을 정해서 다른 모든 정점까지의 최단경로를 구한다. 반면에 플로이드 워셜 알고리즘은 모든 정점을 시작 정점으로 했을 때의 최단경로를 구한다. 따라서 정점 간의 모든 최단거리를 구할 경우에는 플로이드 워셜 알고리즘을 사용한다. 다익스트라 알고리즘은 가중치가 음수인 경우에는 사용할 수 없다. 플로이드 워셜 알고리즘은 가중치가 음수라도 사용이 가능하다. 플로이드 워셜 알고리즘에 대해 먼저 간단히 설명하면 이렇다. 플로이드 워셜 알고리즘에서 시작정점(s)와 도착정점(e)간의 최단거리를 구할 때, 경유하는 정점(t)에 관한 개념이 등장한다. 경유하는 정점(t)이란, 말그대로..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) 이번에는 BFS에 대해서 다뤄볼 것이다. DFS(Depth First Search) - 깊이 우선 탐색 그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이.. lotuslee.tistory.com BFS는 너비 우선 탐색으로 특정 노드와 연결된 모든 노드들을 우선적으로 탐색한 뒤, 그 중에 하나를 선택하여 또 다시 그와 연결된 모든 노드들을 탐색하는 방식으로 진행된다. 하나의 경로만을 깊..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이 파고드는 방식이다. 반면에 BFS 는 넓이를 우선시한다. 특정 노드와 연결된 모든 노드를 한번씩 거친 다음에 다음 노드로 이동하는 방식이다. 예를 들어, 다음과 같은 그래프가 있고 1번부터 탐색을 시작한다고 할 때 왼쪽과 같은 탐색 방법을 DFS, 오른쪽과 같은 탐색 방법을 BFS라고 할 수 있다. DFS : 1 -> 2 -> 4 -> 7 -> 6 -> 3 -> 5 BFS : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 위의 DFS 방식에서 처음에 꼭..

신장 트리(Spanning Tree) : 모든 정점이 간선으로 연결되어 있으면서 사이클이 없는 그래프 예를 들어, 다음과 같은 그래프가 있다고 하자. 위 그래프에서 가능한 신장 트리는 아래와 같다. 1번부터 4번까지의 모든 정점이 연결되있으면서 사이클이 존재하지 않는다. 아래의 경우는 신장 트리가 아니다. 모든 정점이 연결되어 있으나 사이클이 존재하기 때문이다. MST(Minimum Spanning Tree) 신장 트리 중에서 간선의 비용(가중치)의 합이 최소가 되는 것을 최소 신장 트리라고 한다. 위의 그래프에서 6개의 신장 트리 중에 최소 신장 트리는 간선의 비용의 합이 6이 되는 경우이다. MST를 구하는 알고리즘은 대표적으로 2가지가 있다. 1. 프림(Prim) 알고리즘 2. 크루스칼(Kruska..

한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘 주로 간선에 가중치가 주어질 때 사용한다. 단, 다익스트라 알고리즘은 가중치가 음수인 경우에는 적합하지 않다. (이유는 나중에 설명) 우선순위 큐를 이용하지 않고 구현하는 방법과 우선순위 큐를 이용하여 구현하는 방법이 있다. 우선순위 큐를 이용할 때 시간복잡도는 더 줄어든다. 시간 복잡도 : O(N²) 다익스트라 알고리즘을 구현할 때 필요한 몇 가지가 있다. - 시작점과 각 정점들간의 최단거리를 저장하는 이차원 배열 dist[start][end] : start 정점부터 end 정점까지의 최단거리 과정을 진행하면서 계속해서 최단거리를 업데이트하기 때문에 처음에 dist 배열의 모든 요소를 Integer.MAX_VALUE 값으로 초기화해준다. 그리고 새..

그래프 관련하여 문제를 풀다보면(가령 DFS, BFS 문제와 같은) 그래프에서 노드간의 연결관계를 저장해야 하는 경우가 있다. 이럴 때 그래프의 연결관계를 표현하는 방법이 대표적으로 두 가지가 있다. 인접 행렬 인접 리스트 인접 행렬 그래프에 N개의 노드가 있으면, N x N 이차원 행렬을 만들어서 노드와 노드 사이의 간선 가중치를 담는 방식이다. 그래프가 무방향 그래프이고, i노드와 j노드가 연결되어 있으며 둘 사이의 간선의 가중치가 w인 경우, graph[i][j] = graph[j][i] = w 로 나타낼 수 있다. 만약 그래프에 가중치가 주어지지 않은 경우에는 두 노드가 연결되어 있으면 1, 연결되어 있지 않으면 0 으로 나타내어 0과 1로만으로 연결관계를 표현할 수 있다. 혹은 boolean형으..