BOJ 14497 주난의 난

 

문제 링크 : https://www.acmicpc.net/problem/14497

14497번: 주난의 난(難)

 

설명을 이해하는데 시간이 걸렸지만 대략 다음과 같이 해석하면 될 듯하다.

 

문제의 표현

 

'한 겹의 친구를 쓰러뜨린다.'

 

의 의미는 현재 0 인 칸만을 이용해서 도달할 수 있는 1 은 제거할 수 있다가 된다.

(매 단계 도달한 1 은 제거하고 다음 단계로 진행한다.)

그렇다면 출발 지점(*)에서 도착 지점(#)에 이르는데 거치는 1 의 개수의 최소값 +1  을 구하는 문제가 된다.

 

#include<bits/stdc++.h>

using namespace std;

char str[301];
int N,M, grid[301][301], cst[301][301];
int sy,sx,ey,ex;
int dv[]={0,1,0,-1,0};

struct info{
    int cst,y,x;
    bool operator<(const info &rhs) const{
        return cst>rhs.cst;
    }
};

void solve(){
    for(int i=1;i<=N;i++) for(int j=1;j<=M;j++)
        cst[i][j]=INT_MAX;
    cst[sy][sx]=0;
    priority_queue<info> pq;
    pq.push({0,sy,sx});
    
    while(!pq.empty()){
        info tInfo=pq.top();
        pq.pop();
        
        int cy=tInfo.y, cx=tInfo.x;
        if(cy==ey && cx==ex) break;
        if(cst[cy][cx]<tInfo.cst) continue;
        for(int i=0;i<4;i++){
            int ny=cy+dv[i],nx=cx+dv[i+1];
            if(ny<1 || ny>N || nx<1 || nx>M) continue;
            
            if(cst[ny][nx]>cst[cy][cx]+grid[ny][nx]){
                cst[ny][nx]=cst[cy][cx]+grid[ny][nx];
                pq.push({cst[ny][nx], ny,nx});
            }
        }
    }
    
    printf("%d\n", cst[ey][ex]+1);
}

int main(){
    scanf("%d%d",&N,&M);
    scanf("%d%d%d%d",&sy,&sx,&ey,&ex);
    
    for(int i=0;i<N;i++){
        scanf("%s", str);
        for(int j=0;j<M;j++){
            if(str[j]=='1')
                grid[i+1][j+1]=1;
            else
                grid[i+1][j+1]=0;
        }
    }
    
    solve();
}