A응실 보급로 / 다이스트라

1. 다익스트라

2. 힙, 이진트리

3. 피큐

4. 구현하는 방법

5. 메모리 크기 조정

6. 체크 사항 

 

#include <stdio.h>
#define MAX 100
#define H_MAX 20000
#define INF 0x7fffffff

typedef struct _st
{
    int i;
    int j;
    int time;
}P_Queue;

P_Queue heap[H_MAX], st, now, next;
int heapSize;
int N, sol;
int map[MAX + 10][MAX + 10], cost[MAX + 10][MAX + 10];
int rPtr;
int goI[4] = { -1, 0, 1, 0 }, goJ[4] = { 0, 1, 0, -1 };

void Init(void)
{
    heapSize = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cost[i][j] = INF;
        }
    }
    cost[0][0] = 0;
}

void heapPush(P_Queue value, int root)
{
    heap[heapSize] = value;

    int current = heapSize;
    while (current > root && heap[current].time < heap[(current + root - 1) / 2].time)
    {
        P_Queue temp = heap[(current + root - 1) / 2];
        heap[(current + root - 1) / 2] = heap[current];
        heap[current] = temp;
        current = (current + root - 1) / 2;
    }

    heapSize++;
}

P_Queue heapPop(int root)
{
    P_Queue value = heap[root];
    heap[root] = heap[heapSize];

    int current = root;
    while (current * 2 + 1 < heapSize)
    {
        int child;
        if (current * 2 + 2 == heapSize)
        {
            child = current * 2 + 1;
        }
        else
        {
            child = heap[current * 2 + 1].time < heap[current * 2 + 2].time ? current * 2 + 1 : current * 2 + 2;
        }

        if (heap[current].time < heap[child].time)
        {
            break;
        }

        P_Queue temp = heap[current];
        heap[current] = heap[child];
        heap[child] = temp;

        current = child;
    }
    return value;
}

void Input_data()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
}

void BestFS()
{
    rPtr = 0;
    st.i = st.j = st.time = 0;
    heapPush(st, rPtr);
    while (heapSize != rPtr)
    {
        now = heapPop(rPtr++);
        for (int k = 0; k < 4; k++)
        {
            next.i = now.i + goI[k];
            next.j = now.j + goJ[k];
            next.time = cost[now.i][now.j] + map[next.i][next.j];
            if (next.time >= cost[N - 1][N - 1]) continue;
            if (next.i < 0 || next.j < 0 || next.i >= N || next.j >= N) continue;
            if (cost[next.i][next.j] > next.time)
            {
                cost[next.i][next.j] = next.time;
                heapPush(next, rPtr);
            }
        }
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    int tc;
    scanf("%d", &tc);
    for (int t = 1; t <= tc; t++) {
        Input_data();
        Init();
        BestFS();
        printf("#%d %d\n", t, cost[N - 1][N - 1]);
    }
}