[C++][백준 BOJ]2178_미로 탐색.

문제 번호

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

2178번: 미로 탐색

 

 

 

알고리즘 분류

 그래프탐색(BFS)

 

문제 풀이

 그래프 탐색 기법인 BFS를 이용하여 주어진 미로를 탐색하는 문제이다.

BFS를 이용하면 비 가중치 그래프에서 최단경로를 알 수 있다. DIST라는 2차원 배열을 사용한다. DIST배열의 각 원소들은 시작점으로부터 각 좌표까지의 최단경로의 길이를 나타낸다.

 

// BFS
int Solution(int Start_x,int Start_y){
    queue<pair<int,int>> q;
    q.push({Start_y,Start_x});
    Visited[Start_y][Start_x] = true;
    Dist[Start_y][Start_x] = 1;        
    while(!q.empty()){
        // 선입 후출 해서 틀렸었음.....
        int CurrY = q.front().first;
        int CurrX = q.front().second;        
        q.pop();     
        
        // 현재 지점에서 상하좌우 검사해야 할듯.
        for(int next = 0; next<4; next++){            
            // 다음 부분을 방문하지 않았고, 길이 있다면 방문한다.
            if(!Visited[CurrY+dy[next]][CurrX+dx[next]] && Graph[CurrY+dy[next]][CurrX+dx[next]]){                                    
                Visited[CurrY+dy[next]][CurrX+dx[next]] = true;
                q.push( {CurrY+dy[next], CurrX+dx[next]} );
                Dist[CurrY+dy[next]][CurrX+dx[next]] = Dist[CurrY][CurrX] + 1;
            }
        }        
    }
    return Dist[N][M];
}

 

전체 코드

#include<iostream>
#include<queue>
#include<string>
using namespace std;
#define MAX 102
int N, M;
int Graph[MAX][MAX] = {0};
bool Visited[MAX][MAX] = {false};
int Dist[MAX][MAX] = {0};
// 상 우 하 좌
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
// BFS
int Solution(int Start_x,int Start_y){
    queue<pair<int,int>> q;
    q.push({Start_y,Start_x});
    Visited[Start_y][Start_x] = true;
    Dist[Start_y][Start_x] = 1;        
    while(!q.empty()){
        // 선입 후출 해서 틀렸었음.....
        int CurrY = q.front().first;
        int CurrX = q.front().second;        
        q.pop();     
        
        // 현재 지점에서 상하좌우 검사해야 할듯.
        for(int next = 0; next<4; next++){            
            // 다음 부분을 방문하지 않았고, 길이 있다면 방문한다.
            if(!Visited[CurrY+dy[next]][CurrX+dx[next]] && Graph[CurrY+dy[next]][CurrX+dx[next]]){                                    
                Visited[CurrY+dy[next]][CurrX+dx[next]] = true;
                q.push( {CurrY+dy[next], CurrX+dx[next]} );
                Dist[CurrY+dy[next]][CurrX+dx[next]] = Dist[CurrY][CurrX] + 1;
            }
        }        
    }
    return Dist[N][M];
}
int main(){    
    //cin.tie(NULL);
    //ios::sync_with_stdio(false);
    // Y , X 
    cin >> N >> M;
    // 그래프 입력부분.
    for(int i=1; i<=N; i++){
        string Miro; cin >> Miro;
        for(int j=1; j<=Miro.length(); j++){
            Graph[i][j] = Miro[j-1]-'0';
        }
    }
    // 함수 호출.
    cout << Solution(1,1);

    return 0;
}

특이사항

 BFS를 구현할때 Queue를 사용하였다. Queue는 선입선출의 구조인데 선입후출로 잘못 사용해서 오답이 발생했었다.