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

문제 번호

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

2178번: 미로 탐색

 

 

알고리즘 분류

그래프 탐색.

 

문제 풀이

BFS를 사용하여 출발지부터 목적지 까지 최단거리를 구하는 방법을 선택했다.

BFS를 구현할때 Queue를 사용했는데 Queue를 pop하는 과정에서 Front의 값을 pop 해야 하는데 Back의 값을 pop 하여서 오답이 발생하였다.

 Queue는 선입선출의 자료구조임을 기억하자.

 

코드 :

#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;
}

특이사항

-無-