다익스트라(Dijkstra) 알고리즘 ❓
-
다익스트라 알고리즘은 그래프에서 한 정점(노드) 에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.
-
동작 방식
1) 출발 노드와 도착 노드를 설정한다.
2) 최단 거리 테이블을 초기화한다.
3) 현재 위치 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은
노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
4) 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산하여 최단 거리
테이블을 업데이트한다.
5) 3 ~ 4의 과정을 반복한다.
💻 코드로 구현하기
- 코드로 구현하는건 생각보다 쉬운듯 어려웠다. 결국 구현하는데 성공하긴 했지만, 강사님이 구현한 방식과는 완전 다르긴 했다.
- 문제는 내가 구현한 코드로 프로그래머스에서 문제를 풀어보니 테스트 2개를 통과를 못한다... 아무리 생각해도 원인을 모르겠으나... 일단 내가 구현한 코드를 올려본다.
import java.util.*;
public class Dijkstra {
// ✅ 다익스트라 알고리즘 구현하기
int[] cost;
int[] path;
public void findShortestPath(List<List<Integer>> lists, Integer n, Integer startNum) {
// 방문기록을 담을 배열
boolean[] visited = new boolean[n]; // 노드 개수
visited[startNum] = true; // 처음 시작하는 곳은 방문으로 처리
// 출발지부터 목적지 노드까지 갈때 총 거리와 경로를 담을 배열
cost = new int[n];
path = new int[n];
Boolean flag = true;
while(flag) {
flag = false;
Integer index=0;
Integer min = 20000;
// 입력받은 리스트의 사이즈만큼 반복
for(int i=0; i<lists.size(); i++) {
if (startNum == lists.get(i).get(0)) {
if (cost[lists.get(i).get(1)] != 0 && cost[lists.get(i).get(0)] + lists.get(i).get(2) > cost[lists.get(i).get(1)]) {
continue;
} else {
cost[lists.get(i).get(1)] = cost[lists.get(i).get(0)] + lists.get(i).get(2);
path[lists.get(i).get(1)] = lists.get(i).get(0);
}
}
}
// 해당 반복문이 끝난 뒤 cost[] 배열 중 가장 작은 값을 찾는다.
for (int i = 0; i < cost.length; i++) {
if(cost[i] == 0 || visited[i] == true) {
continue;
} else if(min > cost[i]) {
min = cost[i];
index = i;
}
}
startNum = index; // 출발지를 재조정할 변수
visited[index] = true; // 해당 노드는 방문한것으로 처리
// 모든 노드를 방문하면 반복문 종료
for (int i = 0; i < visited.length; i++) {
if (visited[i] != true) {
flag = true;
}
}
}
}
// ✅ 출력 메서드
public void print() {
Integer num=0;
for(int i=0; i<this.cost.length; i++) {
System.out.println(i+"번 노드로 가는 최단 거리 : " + cost[i]);
num = i;
System.out.print(i+"번 노드로 가는 최단 경로 : ");
while (true) {
System.out.print(path[num] + " ");
num = path[num];
if(num==0) {
break;
}
}
System.out.println();
System.out.println();
}
}
}
// ✅ 메인 클래스
import java.util.*;
public class DijkstraMain {
public static void main(String[] args) {
List<Integer> arrayList0 = Arrays.asList(0,1,8);
List<Integer> arrayList1 = Arrays.asList(0,3,7);
List<Integer> arrayList2 = Arrays.asList(0,4,2);
List<Integer> arrayList3 = Arrays.asList(1,5,1);
List<Integer> arrayList5 = Arrays.asList(3,5,8);
List<Integer> arrayList6 = Arrays.asList(3,7,9);
List<Integer> arrayList7 = Arrays.asList(4,6,2);
List<Integer> arrayList8 = Arrays.asList(5,7,4);
List<Integer> arrayList4 = Arrays.asList(6,2,7);
List<Integer> arrayList9 = Arrays.asList(6,7,5);
List<List<Integer>> totalArrayList = new ArrayList<>();
totalArrayList.add(arrayList0);
totalArrayList.add(arrayList1);
totalArrayList.add(arrayList2);
totalArrayList.add(arrayList3);
totalArrayList.add(arrayList4);
totalArrayList.add(arrayList5);
totalArrayList.add(arrayList6);
totalArrayList.add(arrayList7);
totalArrayList.add(arrayList8);
totalArrayList.add(arrayList9);
Dijkstra dijkstra = new Dijkstra();
dijkstra.findShortestPath(totalArrayList, 8, 0);
dijkstra.print();
}
}
-
나는 위와 같이 리스트로 방문 경로를 만들었다. 예를 들어
[0, 1, 8]이면 0번 노드에서 1번 노드까지 가는데 8이라는 비용이 든다는 뜻이다. -
자료구조부터 시작해서 알고리즘 수업까지 진행하면서 느끼는 것이 있다면 내가 생각한대로 코드를 구현하는게 점점 익숙해지는것 같다. 물론 아직 코드 자체는 복잡해보이긴 하나, 그래도 구현에 성공했을때의 짜릿함은 정말 좋은 느낌이다.
-
특히나, 디버깅에 조금씩 익숙해지는것도 코드를 구현하는데 있어 큰 작용을 하고 있다. 디버깅을 통해 오류를 확인하고, 그 오류를 해결하는 것이 정말 중요하다고 본다.
왜냐하면 작성한 코드가 내가 생각한대로 동작을 안하고 있을때 어떤 시점에서 동작이 잘못되는지 확인할 수 있기 때문이다.
오늘의 느낀점 👀
-
오늘로서 짧다면 짧았던 자료구조와 알고리즘 수업이 끝나고 내일부터 본격적으로 스프링 수업을 들어가게 되는데, 가장 하이라이트가 아닐까 싶다. 수업기간도 3주나 되는 만큼 중요한 수업이고 진도도 빠르게 나갈것 같기 때문에 바짝 정신차려서 수업을 따라가야겠다.
-
코딩 자체에 대한 수업은 이제 종료하였지만, 코딩 테스트를 위해서 매주 프로그래머스를 통해 문제를 몇개씩 풀어볼 계획이다. 중요한건 감각을 잃지 않는 것이기 때문에, 꾸준함만이 해결해 줄 수 있는 문제라고 생각한다.
