Heap으로 구현한 Priority Queue

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

#include <iostream>   int map[101][101]; int visited[101][101]; int N;   typedef struct {     int x, y, sum; }HEAP;   HEAP heap[100 * 100 + 1]; int last=0; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };   int push(int x, int y, int sum) {     int c, p;     HEAP tmp;     if (last == 10000) return -1; //가득 찼을 때     heap[++last].x = x;     heap[last].y = y;     heap[last].sum = sum;//데이터 추가     c = last;     p = c / 2;     //부모가 최상위 노드 이전까지     while (p > 0) {         if (heap[c].sum < heap[p].sum) {             tmp = heap[c];             heap[c] = heap[p];             heap[p] = tmp;             c = p;             p = c / 2;         }         else break;     }     return 1; }   HEAP Heap_Pop() {     HEAP tmp,ret;     int c, l, r, p;     if (last == 0) return tmp; //비어있을 때     ret = heap[1]; //최상위 노드     heap[1] = heap[last--]; //마지막 노드를 최상위 노드로 배치                                 //다시 재 정렬 필요     p = 1; l = 2; r = 3;     while (l <= last) { //마지막 노드 이전까지 반복         if (l == last) c = l;         else if (heap[l].sum < heap[r].sum) c = l;         else c = r;         if (heap[c].sum < heap[p].sum) {             tmp = heap[c];             heap[c] = heap[p];             heap[p] = tmp;             p = c;             l = 2 * p;             r = 2 * p + 1;         }         else break;     }     return ret; }   int bfs() {     int i, nx, ny;     HEAP q;     push(0,0,map[0][0]);     visited[0][0] = 1;     while (last>0) {         q = Heap_Pop();         if (q.x == N - 1 && q.y == N - 1) return q.sum;         for (int k = 0; k < 4; k++) {             nx = q.x + dx[k];             ny = q.y + dy[k];             if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;             if (visited[nx][ny]==0) {                 push(nx,ny,q.sum+map[nx][ny]);                 visited[nx][ny] = 1;             }         }       }     return -1; }   void init() {   } int main() {     int i, j;     scanf("%d", &N);       for (i = 0; i < N; i++) {         for (j = 0; j < N; j++) {             scanf("%1d", &map[i][j]);         }     }     printf("%d\n", bfs());     return 0; }   /**************************************************************     Problem: 2093     User: AXQ6548     Language: C++     Result: Accepted     Time:3 ms     Memory:1888 kb ****************************************************************/