[1249번] 보급로

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다익스트라 알고리즘

다익스트라 알고리즘으로 해결 가능하다.

BFS는 불가능한 이유가 해당 정점을 서로다른 위치에서 계속해서 방문해야 할 수 있기에 visit 배열을 쓸 수 없다.

소스 코드 : 

#include <iostream>
 
#define MAX_N 100002
#define MIN(a,b)(a < b ? a : b)
#define SWAP(a,b){INFO t = a; a = b; b = t;}
 
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
 
int arr[102][102];
int dist[102][102];
int n;
 
struct INFO {
    int y;
    int x;
    int cnt;
};
 
class PQ {
public:
    INFO pq[50002];
    int pqCnt;
 
    PQ() {
        pqCnt = 0;
    }
    ~PQ() {
 
    }
    void push(INFO a) {
        pq[++pqCnt] = { a.y,a.x,a.cnt };
 
        int cur = pqCnt;
        int par = cur / 2;
        while (cur > 1 && pq[cur].cnt < pq[par].cnt) {
            SWAP(pq[cur], pq[par]);
            cur = par;
            par = cur / 2;
        }
    }
 
    INFO pop() {
        if (pqCnt == 0)
            return { -1,-1,-1 };
 
        INFO info = pq[1];
        pq[1] = pq[pqCnt--];
 
        int cur = 1;
        int next;
 
        while (1) {
            next = cur * 2;
            if (next < pqCnt && pq[next].cnt > pq[next + 1].cnt) // 무조건 right가 존재한다.(pqCnt까지 힙이 존재하니)
                next++; // 오른쪽 노드가 더 작으면 next를 오른쪽으로 만들어준다.
            if (next > pqCnt || pq[cur].cnt < pq[next].cnt)
                break; // 부모가 자식보다 작은값이면 break(최소 힙 유지)
            SWAP(pq[cur], pq[next]);
 
            cur = next;
        }
 
        return info;
    }
    bool empty() {
        return !pqCnt;
    }
};
 
 
void init() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            arr[i][j] = 0;
            dist[i][j] = 987654321;
        }
    
}
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        PQ pq;
 
        scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%1d", &arr[i][j]);
 
        pq.push({ 0,0,arr[0][0] });
        while (!pq.empty()) {
            INFO here = pq.pop();
    
        
            if (dist[here.y][here.x] < here.cnt)
                continue;
            if (here.y == n - 1 && here.x == n - 1){
                printf("#%d %d\n", tc, here.cnt);
                break;
            }
            for (int i = 0; i < 4; i++) {
                int ny = here.y + dy[i];
                int nx = here.x + dx[i];
                int nextCost = here.cnt + arr[ny][nx];
 
                if (0 <= ny && ny < n && 0 <= nx && nx < n) {
                    
                    if (nextCost < dist[ny][nx]) {
                        dist[ny][nx] = nextCost;
                        pq.push({ ny,nx,nextCost });
                    }
                }                
            }
        }
    }
    return 0;
}