11. 11차시 수업

01.cpp - dijkstra with priority queue(not completed)

/*

priority queue : O(logN)

mininum heap 이용

insert()

1. 맨끝에 삽입.

2. 부모보다 작으면 교환, 크면 멈춤.(반복)

extract()

1. 최소값을 임시 버퍼에 저장.

2. 맨 뒤 노드를 맨 위로 덮어쓰기. (맨 뒤 노드는 없앤다.)

3. (맨 위에서) 좌측노드와 우측노드와 자기 자신 중 최소값과 교환 (반복)

4. 임시 버퍼에 있던 값을 반환

distance배열과 그 값을 이용한 priority queue 두개를 가지고 있어야 한다.

distance값을 업데이트 할때 insert().

최소값 찾을 때 extract() 하는데 뽑아낸 값과 distance배열의 값이 똑같아야 한다.

똑같지 않으면 버리고 다시 extract().

*/

/*

입력 : 시작 끝 거리

0 1 10

0 3 5

1 2 1

1 3 2

3 1 3

3 2 9

3 4 2

2 4 4

4 2 6

4 0 7

distance만 출력하면 0 8 9 5 7

*/

#include <stdio.h>

#define INF 0x7FFFFFFF

int start, finish, arr[1000][1000];

int node_num, edge_num;

int node_left;

int distance[1000];

int precedessor[1000];

int visited[1000];

int priority_queue[1001];//1부터 시작

typedef struct distance_node{

int i;//위치

int n;//값

}Node;

Node D[1001];//오직 distance에만 관련있음.

int Dptr=1;//Dptr=NODE개수

void insert_calc(int node_i){

if(D[node_i].n<D[node_i/2].n){

int tempi, tempn;

tempi=D[node_i].i;

tempn=D[node_i].n;

D[node_i].i=D[node_i/2].i;

D[node_i].n=D[node_i/2].n;

D[node_i/2].i=tempi;

D[node_i/2].n=tempn;

insert_calc(node_i/2);

}

return;

}

void insert(int loc, int num){

D[Dptr].i=loc;

D[Dptr].n=num;

insert_calc(Dptr);

Dptr++;

}

void extract_calc(int k){

if(k*2+1>Dptr) return;

else if(k*2==Dptr){

if(D[k*2].n<D[k].n){

int tempi, tempn;

tempi=D[k].i;

tempn=D[k].n;

D[k].i=D[k*2].i;

D[k].n=D[k*2].n;

D[k*2].i=tempi;

D[k*2].n=tempn;

extract_calc(k*2);

}

else return;

}

else if(D[k*2].n<D[k].n){

if(D[k*2].n<D[k*2+1].n){

//swap with D[k*2]

int tempi, tempn;

tempi=D[k].i;

tempn=D[k].n;

D[k].i=D[k*2].i;

D[k].n=D[k*2].n;

D[k*2].i=tempi;

D[k*2].n=tempn;

extract_calc(k*2);

}

else{

//swap with D[k*2+1]

int tempi, tempn;

tempi=D[k].i;

tempn=D[k].n;

D[k].i=D[k*2+1].i;

D[k].n=D[k*2+1].n;

D[k*2+1].i=tempi;

D[k*2+1].n=tempn;

extract_calc(k*2+1);

}

}

else if(D[k*2+1].n<D[k].n){

//swap with D[k*2+1]

int tempi, tempn;

tempi=D[k].i;

tempn=D[k].n;

D[k].i=D[k*2+1].i;

D[k].n=D[k*2+1].n;

D[k*2+1].i=tempi;

D[k*2+1].n=tempn;

extract_calc(k*2+1);

}

return;

}

int extract(){

int tempi=D[1].i;

int tempn=D[1].n;

D[1].i=D[Dptr].i;

D[1].n=D[Dptr].n;

Dptr--;

extract_calc(1);

if(distance[tempi]!=tempn) return extract();

else return tempi;

}

void search(int cur){

    if (cur == start){

        printf("%d ", start);

        return;

    }

    search(precedessor[cur]);

    printf("%d ", cur);

}

void dijkstra(int cur){

    for (int i = 0; i < node_num; ++i){

        if (arr[cur][i]>0){

            if (distance[cur] + arr[cur][i] < distance[i]){

                distance[i] = distance[cur] + arr[cur][i];

insert(i, distance[i]);

                precedessor[i] = cur;

            }

        }

    }

    visited[cur] = 1;

}

int main(){

    scanf("%d %d", &start, &finish);

    printf("node num : ");

    scanf("%d", &node_num);

    node_left = node_num;

    printf("edge_num : ");

    scanf("%d", &edge_num);

    for (int i = 0; i < edge_num; ++i){

        int a, b, c;

        scanf("%d %d %d", &a, &b, &c);

        arr[a][b] = c;

    }

    //distance 초기화

    for (int i = 1; i <node_num; ++i){

        distance[i] = INF;

    }

    while (node_left > 0){

        int min;

        int first_experiment = 1;//첫번째로 반복문 들어왔으면 min에 수 집어넣어주기

/*

        for (int i = 0; i < node_num; ++i){

            if (visited[i] == 1) continue;

            if (first_experiment){

                first_experiment = 0;

                min = i;

                continue;

            }

            if (distance[i] < distance[min]) min = i;

        }

*/

        dijkstra(extract());

        node_left--;

    }

    //다 끝났으면 역추적 ㄱ

    search(finish);

puts("");

for(int q=0; q<node_num; ++q){

printf("%d ", distance[q]);

}

}

저번에 6차시 수업에선 MAX heap을 다뤘다면 여기선 min heap을 사용합니다. 

완성된 코드가 아니라 제대로 이해했다고 할 수는 없지만 그래도 설명 해보도록 하겠습니다.

priority queue는 우선순위가 있는 큐입니다. min heap을 떠올리시면 숫자가 가장 작은 값이 부모 노드에 오는 완전 이진트리죠. 이 숫자를 우선순위라고 생각하면 그게 priority queue, 즉 우선순위 큐입니다. 

코드 위에 주석에 써져있는 부분을 하나하나 설명드리겠습니다.

insert()

1. 맨끝에 삽입.

2. 부모보다 작으면 교환, 크면 멈춤.(반복)

insert() 함수는 힙에 값을 집어넣는 함수입니다. 힙의 가장 끝에 삽입하고 방금 삽입한 값을 기준으로 그 값이 부모노드의 값보다 작으면 서로 바꿔주고, 아니면 함수를 종료합니다. 이것을 계속 반복합니다.

extract()

1. 최소값을 임시 버퍼에 저장.

2. 맨 뒤 노드를 맨 위로 덮어쓰기. (맨 뒤 노드는 없앤다.)

3. (맨 위에서) 좌측노드와 우측노드와 자기 자신 중 최소값과 교환 (반복)

4. 임시 버퍼에 있던 값을 반환

extract() 함수는 힙에서 값을 추출하는 함수입니다.

첫째로, 힙에서 가장 첫번째 값을 임시버퍼에 저장합니다.

둘째로, 힙에서 가장 마지막 값을 첫번째 노드에 덮어쓰기 한 수 힙의 가장 마지막 값을 삭제합니다.

셋째로, 덮어쓰기된 첫번째 노드부터 시작하여 heapify(), 즉 부모노드의 값을 최소값과 바꾸는 과정을 수행합니다. (정렬하는거죠) 이것을 마지막 노드에 다다르면, 혹은 부모노드의 값과 최소값이 일치하기 전까지 계속 반복합니다.

넷째로, 임시버퍼에 저장한 값을 반환합니다.

distance배열과 그 값을 이용한 priority queue 두개를 가지고 있어야 한다.

distance값을 업데이트 할때 insert().

최소값 찾을 때 extract() 하는데 뽑아낸 값과 distance배열의 값이 똑같아야 한다.

똑같지 않으면 버리고 다시 extract().

이건 주의사항입니다.

다음은 문제입니다. https://www.acmicpc.net/problem/2472 다음시간에 계속~