[BOJ/백준][Gold4] 14923 : 미로 탈출 (C++)

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

14923번: 미로 탈출

 

[난이도] Gold4
[유형] BFS

[풀이]
visit[N][M][k] (k= 지팡이 사용횟수) 배열을 선언해서 현재 지팡이 사용횟수를 저장하는
방식으로 BFS를 돌려주면 된다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14923.cpp

 

#include <cstdio>
#include <queue>
using namespace std;
struct P{int y,x,k;};
int map[1000][1000],N,M,hy,hx,ey,ex,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int visit[1000][1000][2];
int main(){
    scanf("%d%d%d%d%d%d",&N,&M,&hy,&hx,&ey,&ex);
    hy--,hx--,ey--,ex--;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%d",&map[i][j]);
    
    queue<P> q;
    visit[hy][hx][0]=1;
    q.push({hy,hx,0});
    int cnt = 0;
    while(!q.empty()){
        int qsz = q.size();
        while(qsz--){
            auto f = q.front(); q.pop();
            if(f.y==ey && f.x==ex){
                printf("%d",cnt);
                return 0;
            }
            for(int i=0;i<4;i++){
                int ny = f.y+dy[i];
                int nx = f.x+dx[i];
                if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
                if(map[ny][nx]){
                    if(!f.k && !visit[ny][nx][1]) {
                        visit[ny][nx][1]=1;
                        q.push({ny,nx,1});
                    }
                }else if(!visit[ny][nx][f.k]){
                    visit[ny][nx][f.k]=1;
                    q.push({ny,nx,f.k});
                }
            }
        }
        cnt++;
    }
    puts("");
}