[백준] 1753번 최단 경로 (= shortest path) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/1753

알고리즘 : 우선순위 큐zeus-programming.tistory.com/65

우선순위 큐에서 가중치가 가장 낮은 노드를 최상위 부모 노드로 저장하는 이유는

출발 정점 K로부터 현재까지 계산한 값 중 가장 가까운 정점까지의 가중치는 다른 경우의 수에 의해 갱신될 수 없기 때문에

가중치가 가장 적은 정점과 그 가중치를 기준으로 다른 정점까지의 거리를 갱신하기 때문입니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_PQ_SIZE 300001
#define INF 200001

//입력값을 저장할 Node
typedef struct _Node {
    char weight;
    int vertex;
} Node;

typedef struct _vector {
    Node *mem;
    int memSize;
    int back;
} vector;

//시작 정점 K로부터 연결된 정점(vertex)과 그 가중치(weight)가 저장된 priorityQueue의 Data
typedef struct _Data {
    int weight;
    int vertex;
} Data;

typedef struct _priority_queue {
    Data mem[MAX_PQ_SIZE];
    int back;
} priority_queue;

int V;

//입력값 간선이 5 1 2 라면 vec[5]의 mem[vec[5].back]에
//vertex = 1, weight = 2인 노드를 추가한다
int *result;    //시작 정점 K로부터 연결된 정점 1이 가중치 2로 연결되어있다면 result[1] = 2 저장
vector *vec;
priority_queue *pq;

void initData(Data *);
void initPQ(priority_queue *);
bool empty(priority_queue *);
void pop(priority_queue *);
void push(priority_queue *, Data);
size_t size(priority_queue *);
Data top(priority_queue *);
void swapData(Data *, Data *);

void initNode(Node *);
void initVEC(vector *);
void vectorFull(vector *);
void push_back(vector *, Node);
size_t sizeV(vector *);

void Dijkstra(int);
void initResult(int);

int main(void)
{
    //정점의 개수 V, 간선의 개수 E, 시작 정점의 번호 K
    int E = 0, K = 0;
    //입력 받는 간선의 출발 정점 start, 도착 정점 end, 간선의 가중치 weight
    int start = 0;
    pq = (priority_queue *)malloc(sizeof(priority_queue));
    Node tmpNode;

    scanf("%d %d", &V, &E);
    scanf("%d", &K);

    //result 메모리 할당 및 초기화
    vec = (vector *)malloc(sizeof(vector) * (V + 1));
    result = (int *)malloc(sizeof(int) * (V + 1));
    for (int i = 0; i < V + 1; i++)
        initVEC(&vec[i]);
    initResult(V);

    //입력 받을 E개의 간선 vector에 저장
    for (int i = 0; i < E; i++) {
        scanf("%d %d %hhd", &start, &tmpNode.vertex, &tmpNode.weight);

        push_back(&vec[start], tmpNode);
    }

    result[K] = 0;    //자기 자신으로 가는 가중치는 0 저장
    Dijkstra(K);

    for (int i = 1; i <= V; i++) {
        if (result[i] != INF)
            printf("%d\n", result[i]);
        else
            printf("INF\n");
    }

    free(vec);
    free(pq);
    free(result);
    return 0;
}

void initData(Data *data)
{
    data->weight = 0;
    data->vertex = 0;
    return;
}
void initPQ(priority_queue *pq)
{
    for (int i = 0; i < MAX_PQ_SIZE; i++) { initData(&pq->mem[i]); }
    pq->back = 0;
    return;
}
bool empty(priority_queue *pq)
{
    if (!pq->back) { return true; }
    else { return false; }
}
void pop(priority_queue *pq)
{
    if (empty(pq)) { return; }
    pq->mem[1] = pq->mem[pq->back];
    initData(&pq->mem[pq->back--]);
    if (empty(pq)) { return; }

    int parent = 1;
    int child = parent * 2;
    int pqSize = (int)size(pq);

    while (child <= pqSize) {
        if (child + 1 <= pqSize && pq->mem[child].weight > pq->mem[child + 1].weight) { child++; }

        if (pq->mem[parent].weight > pq->mem[child].weight) {
            swapData(&pq->mem[parent], &pq->mem[child]);
            parent = child;
            child = parent * 2;
        }
        else { break; }
    }
    return;
}
void push(priority_queue *pq, Data data)
{
    pq->mem[++pq->back] = data;
    if ((int)size(pq) == 1) { return; }

    int child = pq->back;
    int parent = child / 2;

    while (child > 1) {
        if (pq->mem[parent].weight > pq->mem[child].weight) {
            swapData(&pq->mem[parent], &pq->mem[child]);
            child = parent;
            parent = child / 2;
        }
        else { break; }
    }
    return;
}
size_t size(priority_queue *pq) { return (size_t)pq->back; }
Data top(priority_queue *pq) { return pq->mem[1]; }
void swapData(Data *pData, Data *cData)
{
    Data temp;
    initData(&temp);
    temp = *pData;
    *pData = *cData;
    *cData = temp;
    return;
}

void initNode(Node *node)
{
    node->weight = 0;
    node->vertex = 0;
    return;
}
void initVEC(vector *vec)
{
    vec->mem = (Node *)malloc(sizeof(Node) * 10);
    for (int i = 0; i < 10; i++) { initNode(&vec->mem[i]); } 
    vec->memSize = 10;
    vec->back = 0;
    return;
}
void vectorFull(vector *vec)
{
    vec->memSize *= 2;
    vec->mem = (Node *)realloc(vec->mem, sizeof(Node) * (vec->memSize));
    for (int i = vec->memSize / 2; i < vec->memSize; i++) { initNode(&vec->mem[i]); }
    return;
}
void push_back(vector *vec, Node node)
{
    if (vec->back == vec->memSize)
        vectorFull(vec);
    vec->mem[vec->back++] = node;
    return;
}
size_t sizeV(vector *vec) { return (size_t)vec->back; }

void Dijkstra(int K)
{
    vector *tmpVec;
    Data tmpData;
    tmpData.vertex = K;
    tmpData.weight = result[K];

    push(pq, tmpData);    //먼저 자기 자신으로 가는 것을 검사한다

    while (!empty(pq)) {
        //priorityQueue에서 시작 정점 K로부터 가장 가까운 정점과 가중치 가져옴
        int curV = top(pq).vertex;
        int curW = top(pq).weight;
        pop(pq);

        //예를 들어 vector[1]에 vertex 2로 가는 경로의 가중치가 2, 3, 4인 경우가 있다면
        //result[2]의 값이 INF이므로 priorityQueue 안에 (2, 2), (2, 3), (2, 4)가
        //전부 들어가지만 한 번 (2, 2)인 경우를 계산함으로써 result[2]값이 갱신된다면
        //큐 안의 (2, 3)과 (2, 4)는 계산하지 않고 넘어가게 해준다.
        if (result[curV] < curW) { continue; }

        tmpVec = &vec[curV];

        //정점curV 로부터 연결된 모든 정점들을 검사한다.
        for (int i = 0; i < (int)sizeV(tmpVec); i++) {
            if (result[tmpVec->mem[i].vertex] > curW + tmpVec->mem[i].weight) {
                result[tmpVec->mem[i].vertex] = curW + tmpVec->mem[i].weight;

                tmpData.vertex = tmpVec->mem[i].vertex;
                tmpData.weight = result[tmpData.vertex];
                push(pq, tmpData);
            }
        }
    }
    return;
}
void initResult(int V)
{
    for (int i = 1; i <= V; i++)
        result[i] = INF;
    return;
}