[ALGORITHM] 백준 5827 - What's Up With Gravity

https://www.acmicpc.net/problem/5827

5827번: What's Up With Gravity

대강 해설

캡틴 보비디안이 닥터 비팔로를 만나기 위한 최소한의 flip수를 구하세요.

좌표가 grid cell을 넘어갈시 임무는 실패합니다.

시작 중력은 아래로 작용합니다.(시작시에 공중에 떠 있으면 아래로 떨어집니다.)

중력의 방향은 위 아래로 밖에 뒤집지 못합니다.

옆으로 이동했을 시에 Block Cell이 없을 경우 중력의 방향대로 Block Cell을 만날때 까지 떨어집니다.

C : 현재 Captain Bovidian의 위치

# : 막혀있어 밟을 수 있는 Block Cell

. : 비어있는 Cell

D : Doctor Beefalo의 시작지점 

 

과정

1. C에서 D로 가는 최소한의 값(BFS 다익스트라 활용)
2. 동일한 위치여도 위아래가 막힌경우 중력의 방향이 다를 수 있음.(거리를 저장할 때 중력의 방향도 저장)
3. 맵을 전부 돌았으나 D에 도달하지 못한 경우 -1을 리턴

예제

예제 1

5 5
#####
#...#
#...D
#C...
##.##

정답 : 3

예제 2

15 4
C##.
....
...D
....
....
....
..#.
...#
....
....
.#..
....
..#.
....
##..

정답 : 3

예제 3

5 5
#####
#C...
##...
.....
....D

정답 : 2

코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<climits>

using namespace std;

//g는 중력의 방향 c는 flip의 횟수
typedef struct Dat{
    int y,x,g,c;
}d;

struct compare{
    bool operator()(d &a, d&b){
        return a.c > b.c;
    }
};

int md[2]={1,-1};

char map[501][501];
int dist[501][501][2];
int sy,sx;
int N,M;

void initialize(){
    fill(&dist[0][0][0],&dist[500][500][2],INT_MAX);
}

void input(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>map[i][j];
            if(map[i][j]=='C'){
                map[i][j]='.';
                sy=i;
                sx=j;
            }
        }
    }
}

int bfs(){
    priority_queue<d,vector<d>,compare> pq;

    while(sy>=0&&sy<N&&map[sy+1][sx]!='#'){
        if(map[sy+1][sx]=='D')
            return 0;
        dist[sy][sx][0]=0;
        ++sy;
    }
    pq.push({sy,sx,0,0});

    while(!pq.empty()){
        int y=pq.top().y;
        int x=pq.top().x;
        int g=pq.top().g;
        int c=pq.top().c;


        pq.pop();

        if(dist[y][x][g] < c)
            continue;

        if(map[y][x]=='D')
            return c;

        int mg=md[g];
        if(y+mg>=0 && y+mg<N && map[y+mg][x]=='#'){
            for(int m=0;m<2;m++){
                int ny=y;
                int nx=x+md[m];

                if(nx<0||nx>=M||map[ny][nx]=='#'||dist[ny][nx][g]<=c)
                    continue;

                dist[ny][nx][g]=c;
                pq.push({ny,nx,g,c});
            }

            int tg = g==0?1:0;
            int ty = y + md[g];
            if(ty<0||ty>N-1||dist[ty][x][tg]<=c+1)
                continue;

            dist[ty][x][tg]=c+1;
            pq.push({ty,x,tg,c+1});
        }

        y = y+mg;
        if(y<0||y>=N||dist[y][x][g]<=c||map[y][x]=='#')
            continue;

        dist[y][x][g]=c;
        pq.push({y,x,g,c});
    }

    return -1;
}

void solution(){
    int ret=bfs();
    cout<<ret<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    initialize();
    input();
    solution();

    return 0;
}