[백준]할로윈 묘지(3860)

문제 링크 : [백준]할로윈 묘지(3860)

3860번: 할로윈 묘지

문제 설명

W * H 크기의 묘지가 있고, (0,0)에서 출발하여, 위, 아래, 왼쪽, 오른쪽 한 칸씩 이동하여, (W-1,H-1)까지 최단 시간에 이동하려고 합니다.

묘지에는 묘비들이 있는데, 이 묘비가 있는 곳으로는 가지 못합니다.

또 귀신 구멍이 있어, 귀신 구멍 입구로 들어가게 되면 귀신 구멍 출구로 나가게 되는데 이때 걸리는 시간은 임의의 음수 혹은 임의의 양수가 될 수 있습니다.

최소 시간을 출력하며, 계속 과거로 돌아갈 수 있으면 "Never", 갈 수 없으면 "Impossible" 을 출력합니다.

입력

W H(묘지의 가로, 세로 크기, 1 <= W, H <= 30)

G(묘비의 갯수)

X_i Y_i(묘비의 위치)

E(귀신 구멍의 갯수)

X1_i Y1_i X2_i Y2_i C_i(귀신 구멍의 입구, 출구 위치와 걸리는 시간)

3 3
2
2 1
1 2
0
4 3
2
2 1
3 1
1
3 0 2 2 0
4 2
0
1
2 0 1 0 -3
0 0

 

출력

Impossible
4
Never

 

카테고리

#벨만포드

 

시간 복잡도 상한

O(N⁵)

 

해결 방법

1. 간선 정보는 인접한 칸들의 좌표들로 생성하며, 묘비와 귀신 구멍들의 정보들과 조합하여 필요한 모든 엣지들을 구성합니다.
2. 음수 싸이클이 존재하는 경우, Never를 출력해야하기 때문에 음수 싸이클을 확인 할 수 있는 벨만포드를 이용합니다.
3. 벨만포드를 통하여 도착지까지의 최단 거리를 구하고, 이동 중 음수 싸이클이 발생하였는지를 검사합니다.

시간복잡도

O(N⁴)(N² : 간선의 갯수, N² : 노드의 갯수)

코드

#include<cstdio>
#include<string.h>
#include<vector>
#define D 1e9
using namespace std;
int n,m,g,x,y,a,b,c,d[31][31],w[31][31],o[4][2]={{1,0},{0,1},{-1,0},{0,-1}},i;
struct N{
    N(int x,int y,int a,int b,int c):x(x),y(y),a(a),b(b),c(c){}
    int x,y,a,b,c;
};
std::vector<N>v;
int main(){
    while(1){
        v.clear();
        memset(w,0,sizeof(w));
        for(x=0;x<31;x++)for(y=0;y<31;y++)d[x][y]=D;
        scanf("%d%d",&m,&n);
        if(!n)break;
        scanf("%d",&g);
        while(g--)scanf("%d%d",&x,&y),w[x][y]=1;
        scanf("%d",&g);
        while(g--){
            scanf("%d%d%d%d%d",&x,&y,&a,&b,&c);
            v.push_back(N(x,y,a,b,c));
            w[x][y]=-1;
        }
        for(x=0;x<m;x++){
            for(y=0;y<n;y++){
                if((x==m-1&&y==n-1)||w[x][y])continue;
                for(a=0;a<4;a++){
                    int nx=x+o[a][0],ny=y+o[a][1];
                    if(nx>=0&&nx<m&&ny>=0&&ny<n&&w[nx][ny]<1)v.push_back(N(x,y,nx,ny,1));
                }
            }
        }
        d[0][0]=0;
        for(c=g=1;g<=n*m;g++){
            for(N b:v){
                if(d[b.x][b.y]<D&&d[b.a][b.b]>d[b.x][b.y]+b.c){
                    d[b.a][b.b]=d[b.x][b.y]+b.c;
                    if(g==n*m)c=0;
                }
            }
        }
        if(!c)printf("Never\n");
        else if(d[m-1][n-1]<D)printf("%d\n",d[m-1][n-1]);
        else printf("Impossible\n");
    }
}