글 읽기 - 다익스트라에 대해서 질문 남깁니다

cdt416z 4년 전 0

@djm03178님 갑작스럽게 언급드려서 죄송합니다.. 다익스트라와 우선순위 큐에 대해서 공부중인데 6399890번 소스코드를 보고 이해가 안되서 혹시 짧게라도 시간을 내주실수 있으면 inum[] 함수의 역할과 86~94번째 줄에서 어떻게 서로 다른 두 점 사이의 여러 간선을 선택하는지에 대해서도 알려주실수 있나요..?

inum은 힙 내에서 해당 정점 번호가 저장된 인덱스가 어딘지를 기억하기 위한 배열이고, 이를 통해서 힙에 중복된 정점을 삽입하는 일 없이 기존 지점에서 최단 거리가 변할 때마다 그에 맞게 위쪽으로 이동시킬 수 있게 됩니다. 중복된 정점이 힙에 들어갈 수 있게 구현하는 경우 시간 복잡도가 ElogV가 되는데, 이 방법을 사용하면 VlogV로 줄일 수 있게 됩니다.

해당 구현체는 힙에 정점 번호만을 넣고 거리를 비교할 때는 w라는 배열을 통해 우선순위를 정하는데, 시작 정점과 연결된 정점들에 대한 링크드 리스트를 순회하면서 거리를 갱신하고 아직 힙에 넣지 않은 정점들을 넣어주는 부분입니다. 사실 그 부분에서 실수가 있어서 힙 구조가 유지되지 않게 되는 경우가 존재하기는 하는데... 저격이 가능한지는 모르겠네요.

cdt416z 4년 전 0

@djm03178 긴글 감사드립니다!!

1학년때 구조체와 힙 등을 다 배워놓고 정작 다익스트라를 힙을 통해 구현하는 방법에 대해 모르니 참 난해했는데 보고 어느정도 이해 했습니다.. 이제 혼자 구현해봐야지요 사실 이 코드를 보고 1916번을 도전중인데 이제 push와 pop 함수를 힙을 사용해 어떻게 구현해야할지 감을 잡은거 같습니다. 열심히 해보겠습니다! 다시한번 감사드려요!!

cdt416z 4년 전 0

감사합니다 덕분에 1시간만에 1916번 풀었습니다!! 이제야 다익스트라 알고리즘에 대해서 완벽하게 이해했네요

구조체로 푸는건 아직 익숙하지 않아서 더 연습해봐야할거같습니다 감사합니다!!~!~!~!~!~!

#include <stdio.h>
#define INF 987654321
#define SWAP(a, b) {int t; t = a; a = b; b = t;}

int N, M, here, go, dweight;
int map[1001][1001] = { 0 };
int line[1001] = { 0 };
int heap[100000][2];
int index = 0;

void push(int weight, int num){
    heap[++index][0] = weight;
    heap[index][1] = num;
    for(int i = index; i > 1; i /= 2){
        if(heap[i][0] < heap[i / 2][0]){
            SWAP(heap[i][0], heap[i / 2][0]);
            SWAP(heap[i][1], heap[i / 2][1]);
        }
        else{
            break;
        }
    }
}

int pop(){
    dweight = heap[1][0];
    int ret = heap[1][1];
    heap[1][0] = heap[index][0];
    heap[1][1] = heap[index][1];
    heap[index][0] = 0;
    heap[index--][1] = 0;
    for(int i = 1; i * 2 <= index;){
        if(i * 2 + 1 > index){
            if(heap[i][0] > heap[i * 2][0]){
                SWAP(heap[i][0], heap[i * 2][0]);
                SWAP(heap[i][1], heap[i * 2][1]);
            }
            break;
        }
        if(heap[i][0] <= heap[i * 2][0] && heap[i][0] <= heap[i * 2 + 1][0]){
            break;
        }
        else if(heap[i][0] <= heap[i * 2][0]){
            SWAP(heap[i][0], heap[i * 2 + 1][0]);
            SWAP(heap[i][1], heap[i * 2 + 1][1]);
            i = i * 2 + 1;
        }
        else if(heap[i][0] <= heap[i * 2 + 1][0]){
            SWAP(heap[i][0], heap[i * 2][0]);
            SWAP(heap[i][1], heap[i * 2][1]);
            i = i * 2;
        }
        else{
            if(heap[i * 2][0] < heap[i * 2 + 1][0]){
                SWAP(heap[i][0], heap[i * 2][0]);
                SWAP(heap[i][1], heap[i * 2][1]);
                i = i * 2;
            }
            else{
                SWAP(heap[i][0], heap[i * 2 + 1][0]);
                SWAP(heap[i][1], heap[i * 2 + 1][1]);
                i = i * 2 + 1;
            }
        }
    }
    return ret;
}

void stra(int num){ // num이 첫 도시
    heap[++index][0] = 0; // 현재까지의 중첩 가중치
    heap[index][1] = num; // 가는 도시
    while(index){ // index가 0이 아닐동안
        int ret = pop();
        // dweight는 중첩 가중치
        // pop을 하면서 중첩 가중치와 가는 도시 소환
        if(dweight > line[ret]){
            continue;
        }
        line[ret] = dweight;
        for(int i = 1; i <= N; i++){
            if(ret != i && map[ret][i] != -1){
                push(line[ret] + map[ret][i], i);
            }
        }
    }
}

int main(){
	scanf("%d %d", &N, &M);
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			map[i][j] = -1;
		}
	}
    for(int i = 0; i < M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(map[a][b] == -1){
            map[a][b] = c;
        }
        else{
        	map[a][b] = map[a][b] < c ? map[a][b] : c;
        }
    }
    scanf("%d %d", &here, &go);
    for(int i = 1; i <= N; i++){
        line[i] = INF;
    }
    line[here] = 0;
    stra(here);
    printf("%d", line[go]);
    return 0;
}

djm03178 4년 전 0

위에 잘못 설명한 것이 있어서 정정합니다. 제 방법은 VlogV로 줄어드는 것이 아니라 ElogE를 ElogV로 줄이는 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다익스트라에 대해서 질문 남깁니다

cdt416z 4년 전 0

djm03178 4년 전 1

cdt416z 4년 전 0

cdt416z 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말