최간거리 찾기 알고리즘 중, 유명한 다익스트라 알고리즘을 정리해봅니다!

[ 다익스트라 알고리즘(Dijkstra Algorithm) ]

 + 음의 가중치가 없는 그래프에서 한 정점에서 다른 정점까지의 모든 최단거리를 구하는 알고리즘입니다.

 + '순차적(일반)' 과 '우선순위 큐', 두 가지 방법으로 나타낼 수 있습니다.

[ 조건 ]

 + 음의 가중치가 없어야 합니다.

 + 알고리즘 시작 시, 시작 점에서 모든 점까지의 거리는 Inf(Infinity,무한대)로 설정합니다.

[ 기본 로직 ]

 + 시작 정점을 기준으로 연결된 모든 정점들을 까지의 가중치를 비교해가며, 최단거리를 갱신합니다.

 + 시작 정점에서 각 정점까지의 최단거리를 저장하는 배열(Distance)을 만듭니다.

 + "현재 정점에서 가지고 있는 최단거리 vs 다른 정점에서 현재 정점까지 계산한 최단거리" 를 계산해서 최단 거리를 Update합니다.

 + 위의 비교에서 '기존의 최단거리'가 더 짧으면 연산을 하지 않습니다.

 + 다음 정점을 선택 시, 방문하지 않은 정점 중, 가장 짧은 거리의 정점을 선택해서 계산합니다.

[ 순차적(일반) 알고리즘 ]

 + 먼저, 예시 그래프를 하나 준비합니다. 시작 정점은 '5'번 입니다.

+ 아무런 작업을 하지 않았기에 모든 정점과의 거리는 Inf(Infinity, 무한대)입니다.

 + 시작 정점을 기준으로 시작해보면,

1) 5번과 연결된 정점은 2,4번입니다.

2) 각각의 정점과의 최단거리를 비교합니다.

3) 2번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(Inf, 0+4) = 4

4) 4번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(Inf, 0+2) = 2

 +연산이 끝나고나면 그래프가 Update됩니다.

 + 5번 정점과 연결된 정점 중, 탐색하지 않았고, 가장 짧은 정점 4번을 탐색합니다.

1) 4번과 연결된 정점은 2,3번입니다.

2) 각각의 정점과 최단거리를 비교합니다.

3) 2번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(4, 2+1) = 3

4) 3번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(Inf, 2+1) = 3

 + 연산이 끝나고나면 그래프가 Update됩니다.

 + 방문하지 않은 정점 중, 가장 짧은 거리의 정점이 2번이므로 2번부터 계산합니다.

 + 이와 같은 연산을 끝까지 하고나면 모든 점까지의 최단거리를 구할 수 있습니다.

[ 우선순위 큐(힙구조) 알고리즘 ]

 + 우선순위 큐를 이용한 방식의 알고리즘은 '우선순위 큐'를 이용해 항상 최소거리의 정점을 우선적으로 계산하는 알고리즘입니다.

 + 위의 순차적 알고리즘에 비해 더욱 빠른 연산이 가능합니다. 왜나하면 최소 힙을 이용하여 더욱 빠르게 최소거리의 정점(다음 탐색할 곳)을 찾을 수 있기 때문입니다.

 + 우선순위를 이용하면, 최소거리부터 계산하게되어 미리 최단거리를 구할 수 있어, 차후 불필요한 연산을 줄일 수 있습니다.

 + 일반적인 구조는 순차적 알고리즘과 동일하며, 우선순위 큐를 쓴다는 점만 다릅니다.

1) 우선순위 큐에서 Pop합니다.

2) 방문한 곳인지 확인합니다. 방문하지 않았으면 방문한 곳으로 표시합니다.

3) 현재 정점(A)의 최소거리와 비교합니다. Min(기존 최소거리, 이전 정점 최소거리 + distance)

4) 기존 최소거리가 더 작으면 연산을 하지않고, 그렇지 않으면 연산합니다.

5) 연산하게 되면, 현재 정점(A)과 연결된 정점(B) 중, 기존 최소거리(B)보다 작아지는 정점들을 큐에 집어 넣습니다. Min(기존 최소거리(B), 이전 정점 최소거리(A) + distance)

 + 순차적 알고리즘보다 빠른 연산이 가능합니다!

   - 자세한 시간복잡도 비교는 나중에...

*** 참고해야할 점

 - 가중치가 음수인 경우에는 벨만-포드 알고리즘을 사용해야 합니다.

 - 다익스트라 알고리즘은 항상 최소거리를 우선으로 연산하기 때문에, 한 정점을 두 번 지나는 최소거리는 나오지 않습니다.(왜나햐면 그 지점을 지나가면 무조건 최소거리보다 많이 나오기 때문입니다.)

Q. 왜 탐색한 곳을 표시해서 나중에 계산하지 않나요? 나중에 다른 루트를 통해 더욱 짧은 거리가 생길 수 있지 않나요??

A. 최단거리를 최우선으로 연산하기 때문에, 이미 방문한 점을 재 방문한 루트는 무조건 기존의 루트보다 거리가 클 수 밖에 없습니다. 그러니 비교 연산 조차 해 줄 필요가 없습니다.

[Code]

+ https://www.acmicpc.net/problem/1753의 문제 풀이과정을 사용했습니다.

Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.

  그래프 탐색에는 여러 알고리즘이 있지만, 가장 대표적으로 DFS와 BFS가 있습니다.

  <간단 비교>

 + DFS(Depth First Serch)

   - '깊이 우선 탐색';

   - 현재 정점에서 갈 수 있는 점들 중, 한 곳을 우선적으로 끝까지 탐색;

   - 스택이나 재귀함수로 구현;

 + BFS(Breadth First Serch)

   - '너비 우선 탐색';

   - 현재 정점에서 갈 수 있는 점들부터 탐색;

   - 큐를 이용해서 구현;

 [ DFS ]

 + DFS는 Depth First Search로 '깊이 우선 탐색'이라는 뜻의 알고리즘입니다. 말 그대로 한 점에서 갈 수 있는 곳을 최우선으로 파고들어간 다음, 다음 정점으로 가 그 정점에서의 끝까지 탐색합니다.

 + DFS 구현을 위해서 대부분 '스택'과 '재귀함수'를 이용합니다. 왜냐하면 처리 구조가 DFS와 같기 때문입니다. 밑의 그림을 참고해주세요.

 + 표에서 나오는 바와 같이, 

1) A에서 갈 수 있는 곳 X가 스택에 들어가고,

2) 그 다음 X에서 갈 수 있는 H,G가 스택에 들어갑니다.

3) 그 다음, LIFO(Last In, First Out)이므로 H에서 갈 수 있는 EPG가 스택에 들어갑니다. 여기서 G는 이미 스택에 쌓여있기에 스택에 추가되지 않습니다. 

 + 이런 식으로, 스택의 가장 위에있는 정점에서 갈 수 있는 정점들을 스택에 집어넣고 그곳을 탐색하는 것을 반복해서 모두 탐색하는 것이 DFS입니다.

 + 만약 정점 간에 부모, 자식 관계가 있다면, 같은 부모는 스택에 넣고 자식부터 탐색하는 것이 DFS입니다.

 *** 참고해야할 점

 - 방문했던 정점을 재 탐색 하지 않기위해, 따로 배열을 만들어서 방문한 곳인이 체크해야합니다.

 - 완전 탐색 입니다.

 - 트리에서 최단 거리 탐색 가능합니다.

 - 가중치 및 비가중치 그래프에서는 거의 사용되지 않습니다.(불가능하다, 가능은하나... 와 같은 여러 의견들이 있습니다)

[ BFS ]

 + BFS는 Breadth First Search로 '너비 우선 탐색'을 뜻하는 알고리즘입니다. 위에서 말씀드린 DFS와는 달리, 현재 정점에서 갈 수 있는 곳들을 다 탐색하고, 탐색한 곳에서 갈 수 있는 정점들을 탐색합니다.

 + BFS 구현을 위해서 대부분 '큐'를 이용해 구현합니다. 왜냐하면 처리 구조가 BFS와 같기 때문입니다.

 + 표에서 보이는 바와 같이

1) A에서 갈 수 있는 곳 X가 큐에 들어가고,

2) X에서 갈 수 있는 H,G가 큐에 들어갑니다.

3) 그 뒤, H,G를 탐색하면서 해당 정점에서 갈 수 있는 정점들을 큐에 넣습니다.

 + 이런 식으로 정점에서 갈 수 있는 정점들을 먼저 탐색한 뒤, 탐색한 정점들에서 갈 수 있는 정점을 탐색하는 것을 반복해서 모두 탐색하는 것이 BFS 알고리즘 입니다.

 *** 참고해야할 점

 - 방문했던 곳을 재 방문 하지않기위해, 따로 배열을 만들어서 체크해야합니다.

 - 완전 탐색입니다.

 - 트리에서 최단거리 탐색이 가능합니다.

 - 비가중치 그래프에서 최단거리 탐색이 가능합니다. (다익스트라보다 효율이 좋다고 합니다.)

 - 가중치 그래프에서는 잘 사용되지 않습니다.

[ Code ]

 + https://www.acmicpc.net/problem/1260 문제의 풀이 과정으로 사용했습니다.

Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.

  "DP문제에서 배열은 0번이 아닌 1번 부터 사용하자!!!"

 일반적으로 우리가 알고리즘 문제를 풀 때, 0부터 접근해서 반복문을 돌리던, 값을 바꾸던 한다. 
그러나 DP에서는 1부터 접근하는게 더 효율적이거나 가독성이 좋을 수 있다.

  일반적으로 DP는 점화식을 찾는 것부터 시작되는데, 이 점화식은 1번부터 시작하는 경우가 많다. 만약 이러한 경우에서 반복문을 0부터 돌리게 된다면, i + 1 이 기본 접근 방식이 되어 가독성이 떨어질 수 있을 뿐더러, i - 1번 째에 접근할 때, i가 0이라면 -1번째에 접근하게되 따로 예외처리를 해줘야 한다. 하지만 1번 부터 시작하게 된다면, 자연스럽게 i - 1이 0번째로가 다른 예외처리 없이 똑같이 끝까지 실행시킬 수 있다.

  보는 바와 같이 코드 길이 뿐 아니라 가독성에서도 차이가 확 벌어진다.

  따라서, DP문제에서 점화식을 찾았다면, 배열을 0이 아닌 1부터 사용하는 것이 좀 더 유용할 것이다.