미로 탈출

'이것이 코딩테스트다 with 파이썬' 실전 문제 5-4입니다.

 

미로나 이동하는 문제는 BFS를 많이 사용하는 것 같다.

아직 미숙해서... 문제가 너무 어렵다ㅠ

 

 

□ 소스 코드

#include <bits/stdc++.h>

int N,M;
int** mazeInput;

int mazeBFS(int x, int y){
    queue<pair<int, int>> mazeQueue;
    
    mazeQueue.push({x,y});
    
    int mvX[] = {-1,0,1,0}; //상,좌,하,우
    int mvY[] = {0,-1,0,1};
    
    while(!mazeQueue.empty()){
        x = mazeQueue.front().first;
        y = mazeQueue.front().second;
        mazeQueue.pop();
        
        for(int i=0;i<4;i++){
            int afterX = mvX[i] + x;
            int afterY = mvY[i] + y;
            
            if(afterY < 0 || afterX <0 || afterY >= M || afterX >= N )
                continue;
            if(mazeInput[afterX][afterY] == 0)
                continue;
             if(mazeInput[afterX][afterY] == 1){
                mazeInput[afterX][afterY] = mazeInput[x][y] +1;
                mazeQueue.push({afterX,afterY});
                
            }
            
        }
    }
    return mazeInput[N-1][M-1];
}


void maze(){
    cin>>N>>M;
    
    mazeInput = new int* [N];
    for(int i=0;i<N;i++)
        mazeInput[i] = new int [M];
    
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            scanf("%1d",&mazeInput[i][j]);
    
    
    cout<<mazeBFS(0,0)<<endl;
    
    for(int i=0;i<N;i++)
        delete [] mazeInput[i];
    delete [] mazeInput;
}

 

해결 방법

시작 지점과 도착 지점이 고정되어 있으므로 우리가 고려해야 할 상황은 범위를 벗어나는 것과 미로에 있는 괴물(0)을 만나지 않는 것이다.

큐를 이용하여 탐색하는데 마지막 도착지점에서 몇 번에 걸쳐서 왔는지 알기 위해 1로 주어진 값을 더하다 보면 도착지점에 변경된 값이 가장 최단 경로로 도착한 결과물이다.

따라서 상하좌우로 이동하는 것을 배열로 만들어 반복문을 돌리면서 다음 칸이 괴물이 있는지 확인하고 없거나 범위를 넘지 않는 경우

이전에 저장된 값에 1을 더한 값을 현재 칸에 저장한다.

 

끝.