최단거리🌉 - 다익스트라 Dijkstra

▶ 유형

• 한 정점을 기준으로 도착 정점 까지의 최단 경로 트리를 만드는 것
• 가중치가 없는 다익스트라는 BFS
• 우선순위 큐를 사용하지 않으면 O(V^2), 사용하면 O(E+VlogV)가 된다(V는 정점개수,  E는 간선 개수)

새 정점을 방문할 때, 그 정점에 인접해있는 정점이 이미 방문한 정점이라면 저장돼있는 경로 가중치와 새 정점을 경유해서 방문하는 가중치를 비교해 더 가까운 경로로 갱신한다. 경유한다는 개념이 필요한데, 출발 정점도 자기 자신을 경유해서 최소 값을 담는다는 개념으로 접근하면 된다.

 

우선순위 큐를 사용해서 다익스트라를 구현한 의사코드를 먼저 보자

이때 source는 출발정점이다. while 부분이 구현인데, 최소 힙으로 된 우선순위 큐에서 하나 뽑고, 그 정점의 인접 정점들을 돌면서 현재 정점을 경유해서 가는게 빠른지(가중치 합이 적은지) 경유안하는게 빠른지 비교해서 출발 정점에서 도착 정점까지의 각 정점 사이 최단거리 합이 들어있는 dist배열에 기록한다.

▶ 전략

틀을 외우는 게 나을 것 같다.

출발 정점 - 도착 정점 두개만 생각하기 보다 무조건 도착 정점만 보고 돌려야 덜 헷갈린다.

static class Node {
    int end, w;
    
    Node(int to, int w) {
        this.end = to;
        this.w = w;
    }
}
 
static PriorityQueue<Node> pq;
static List<Node>[] list;
static int[] dist;
static int v;
static int e;

도착 정점과 거기까지의 가중치를 들고다닐 Node 클래스를 하나 만든다.

PriorityQueue를 Min-Heap으로(오름차순)로 만들어 주고, 각 정점에 인접한 정점들을 리스트에 담은 배열을 선언해서, 인접 리스트를 생성한다.

그리고 각 정점에 방문했을 때의 최적값을 담을 dist배열도 선언한다.

 

의사코드에 적혀있는 초기화 과정처럼 진행하려면

		int INF = 100000000;
		list = new ArrayList[v + 1];
		dist = new int[v + 1];

		Arrays.fill(dist, INF);
		for (int i = 1; i <= v; i++) {
			list[i] = new ArrayList<>(); // 각 노드(정점)에 연결된 리스트 생성
		}

		pq = new PriorityQueue<Node>((o1, o2) -> {
			return o1.w - o2.w;
		});

dist배열을 도달할 수 없는 값으로 먼저 초기화 해두고, pq를 min-heap으로 만들어준다.

 

이제 다익스트라를 보자.

	static void dijkstra(int start) { // 시작 점은 end가 0이다.
		boolean[] vis = new boolean[v + 1];
		pq.add(new Node(start, 0));
		dist[start] = 0;
		while (!pq.isEmpty()) {
			Node curNode = pq.poll();
			int cur = curNode.end; // 현재 노드에서 어디로 갈지를 보는 게 중요함

			if (vis[cur] == true)
				continue;
			vis[cur] = true;

			for (Node node : list[cur]) {
				int tmpW = dist[cur] + node.w;
				if (dist[node.end] > tmpW) {
					dist[node.end] = tmpW;
					pq.add(new Node(node.end, dist[node.end]));
				}
			}
		}
	}

시작 정점을 넣을 때, 이때의 거리 값은 당연히 0이고 어디 이동하는 것도 아니니까 dist[start]에도 0이 들어간다.

이 과정에서 vis 배열이 하나 더 필요하다. 이미 방문한 정점에 도착해서 인접리스트를 돌지않도록 하는 과정인데, 다익스트라는 이미 도착한 지점에서의 최단경로를 보장하기 때문에 불필요한 탐색을 막기위해 설정하는 장치라고 볼 수 있다.

 

이제 도착한 정점의 인접리스트(그 정점과 인접한 모든 정점들)을 순회한다.

그 정점으로 바로 가는 값과, 현재 정점을 경유해서 그 정점으로 가는 값을 비교하려고 tmpW에 값을 담는다. node.w는 도착한 정점에 인접한 정점의 가중치이고, 도착한 정점까지의 가중치를 더해서 경유한 값을 미리 저장한 게 tmpW다.

 

이걸 dist[node.end]와 비교한다. dist[node.end]는 도착한 정점과 인접한 정점까지의 현재 최단 경로가 담겨있는데, 이걸 갱신하게 되면 갱신해서 pq에 다시 넣어주면 된다. 

 

내가 개인적으로 다익스트라에서 어려워하는 건, 입력이 정점 - 정점 - 가중치 형태가 아니라, map으로 줄 때다. 간선형태를 다 만들어야하나? 하는 고민에서 부터 생각이 꼬이기 시작하는 데, 아래와 같은 방식으로 해결하자.

 

Node의 형태부터 바꿔야한다. 출발 정점, 도착 정점을 기록한다.

dist도 2차원 배열로 선언하고, 모든 dist 원소에 INF를 넣어준다. 총 정점 개수, 간선개수는 map에 따라 달라지지만 기본적으로 nxn일 때 아래 선언한 것과 같다.

static class Node{
    int s;
    int e;
    int d;
     
    Node (int s, int e, int d) {
        this.s = s;
        this.e = e;
        this.d = d;
    }
}

static int dist[][];
v = n * n;// 정점 개수는 map 칸 개수
e = n * (n - 1) / 2; // 총 간선 개수

// main에서
for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    dist[i][j] = INF;
                }
            }

이제 중요한 부분이다.

가중치가 없는 다익스트라는 BFS라고 위에서 적어놨다. map을 주고 최단경로를 찾으라는 문제는 BFS처럼 작동해야 되기때문에 방향배열을 만들고, 유효범위 안에서 방향을 돌며 최단 거리를 찾아야한다.

static int[] di = { -1, 0, 1, 0 };
static int[] dj = { 0, 1, 0, -1 };

public static void dijkstra() {
        pq.add(new Node(0, 0, dist[0][0]));
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            int ci = now.s;
            int cj = now.e;
            int d = now.d;
            if(d > dist[ci][cj])continue;
            for(int i=0;i<4;i++) {
                int ni = di[i] + ci;
                int nj = dj[i] + cj;
                if(ni>=0 && ni<n && nj>=0 && nj<n) {
                    if(dist[ni][nj] > dist[ci][cj] + map[ni][nj]) {
                        dist[ni][nj] = dist[ci][cj] + map[ni][nj];
                        pq.add(new Node(ni,nj,dist[ni][nj]));
                    }
            	}
        	}
    	}
	}
    

(0,0) -> (n-1.n-1) 로 갈 때의 최단거리를 구하는 다익스트라다. 

틀은 같지만, 인접리스트를 통해 비교하던것이 방향배열을 돌면서 비교하는 것으로 바뀌었다. 최단거리 값 갱신하는 부분은 이 코드가 더 눈에 잘들어오는 것 같기도 하다.

 

인접리스트, 인접행렬 모두 중요한 건 갱신하는 부분이다. 

먼저 인접행렬

if(d > dist[ci][cj])continue;
            for(int i=0;i<4;i++) {
                int ni = di[i] + ci;
                int nj = dj[i] + cj;
                if(ni>=0 && ni<n && nj>=0 && nj<n) {
                    if(dist[ni][nj] > dist[ci][cj] + map[ni][nj]) {
                        dist[ni][nj] = dist[ci][cj] + map[ni][nj];
                        pq.add(new Node(ni,nj,dist[ni][nj]));
                    }
            	}
        	}

그다음 인접 리스트다.

boolean[] vis = new boolean[v + 1]; // 방문체크할 배열 함수 스코프 내에서 선언

if (vis[cur] == true)
				continue;
			vis[cur] = true;

			for (Node node : list[cur]) {
				int tmpW = dist[cur] + node.w; // dp푸는 것 처럼 dist값과 비교해야된다.
				if (dist[node.end] > tmpW) {
					dist[node.end] = tmpW;
					pq.add(new Node(node.end, dist[node.end]));
				}
			}

틀을 잘 외워서 풀자.

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^