[백준]미로에 갇힌 건우(18224)

문제 링크 : [백준]미로에 갇힌 건우(18224)

문제 설명

N * N 지도가 주어집니다.
0은 빈 칸, 1은 벽입니다.
(1,1)에서 출발하여, (N,N)까지 이동하는데, 벽은 밤에만 넘어갈 수 있고, 진행 방향으로 이어진 벽을 한번에 넘어가야 합니다.
벽을 타고 나면서 지도를 벗어나는 경우는 이동할 수 없습니다.
밤/낮에 몇칸을 이동 할 수 있는지가 주어졌을 때, 목적지로 가장 빠르게 이동하였을 때, 몇번째 날의 낮/밤 여부를 구하세요.

입력

N(지도의 크기, 1 <= N <= 500)
M(밤/낮의 길이, 1 <= M <= 10)
B_ij(벽의 여부)

5 2
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0

출력

2 sun

카테고리

#다익스트라 #DP #구현

시간 복잡도 상한

O(N² * M * logN²)

해결 방법

1. 전체적인 큰 흐름은 다익스트라를 통하여 최단거리를 구합니다.
2. 밤인 경우와 낮인 경우에 따라서 갈 수 있는 노드가 다르기 때문에 밤인지 낮인지에 대한 정보가 있어야 합니다.
3. 그리고 밤,낮이 몇번이 지속되었는지 혹은 몇번 남았는지에 대한 정보도 있어야 칸을 이동하면서 밤낮이 바뀌는 타이밍을 알 수 있습니다.
4. 그리고 일반적인 다익스트라와 달리 다른 곳을 들렀다가 오는 경우가 최단거리도 될 수 있기 때문에, 밤/낮, 그리고 각각이 몇번 지속되었는지에 따라 최단거리를 따로 저장해야 합니다.
5. 위 코드들을 잘 구현하면 됩니다.

시간복잡도

O(N² * M * logN²)

코드

#include<iostream>
#include<queue>
using namespace std;
int n,m,i,j,o[4][2]={{1,0},{0,1},{-1,0},{0,-1}},x,y,ns,nm;
bool d[500][500],v[500][500][2][10];
struct N{
    N(int c,int m,int x,int y,int s):c(c),m(m),x(x),y(y),s(s){}
    int c,m,x,y,s;
};
queue<N>q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;m--;
    for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>d[i][j];
    q.push(N(1,m,0,0,1));
    v[0][0][1][m]=1;
    while(!q.empty()){
        N c=q.front();q.pop();
        if(c.x==n-1&&c.y==n-1){
            cout<<c.c<<(c.s?" sun":" moon");
            return 0;
        }
        for(i=0;i<4;i++){
            x=c.x+o[i][0];y=c.y+o[i][1];
            ns=c.m?c.s:!c.s;nm=c.m?c.m-1:m;
            if(x<0||y<0||x>=n||y>=n||v[x][y][ns][nm])continue;
            if(c.s&&d[x][y])continue;
            for(;x<n&&y<n&&x>=0&&y>=0&&d[x][y];x+=o[i][0],y+=o[i][1]);
            if(x<n&&y<n&&x>=0&&y>=0){
                q.push(N(c.c+(!c.s&&!c.m),nm,x,y,ns));
                v[x][y][ns][nm]=1;
            }
        }
    }
    cout<<-1;
}