62. C++ 백준 2178 번 미로 탐색 자세한 설명

안녕하세요 코딩하는 덕구입니다.

C++ 백준 2178 번 미로 탐색 입니다.

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

2178번: 미로 탐색

 

DFS, BFS 아무거나 사용하면 되는거 아니냐고 하실 수 있는데

DFS를 마구잡이로 사용하시면 안됩니다.

마구잡이로 사용하면 최단거리가 아닌 첫 번째로 해결하는 값이 출력되기 때문이죠

 

최단거리 문제는 BFS 로 푸시면 됩니다.

입구 부분에서 출구 부분에 가까워지면서 최단거리를 구할 수 있기 때문이죠.

 

BFS는 Queue로 구현 하실 수 있습니다.

 

BFS와 DFS를 어떻게 구현하시는지 궁금하신 분들은

 

이 예제를 풀어보시고, 제 글의 설명을 읽어보시는 것을 추천드립니다.

https://programmersdiary.tistory.com/77

60. C++ 백준 1260 번 DFS 와 BFS

 

먼저 미로를 그려야 됩니다. 추후에 말이 이동하면서 (x, y 좌표로 표현) 길이 있는지 아닌지 확인하기 위함이죠

int N, M;
string row;
cin >> N >> M;
for (int i = 0; i<N; i++){ //미로 입력
    cin >> row; //string으로 한번에 입력 받고
    for (int j = 0; j<M; j++){
        maze[i][j] = row[j] - '0'; //각 글자에 접근하여 숫자로 변환해서 maze에 입력
    }
}

 

입력 양식에 맞게 행렬로 입력받습니다.

 

이후 BFS를 구현하기 위해 queue를 선언합니다.

#include <queue>

queue<pair<int, int>> loc; //미로 안의 위치

 

 

시작좌표인 0,0을 삽입해줍니다.

loc.push(make_pair(0,0));

 

 

본격적으로 미로찾기 시작입니다.

loc에는 다음에 방문할 좌표들이 저장되어 있습니다.

loc이 비어있지 않다면 while문을 계속 반복하고, 

loc (큐) 안에 들어있는 좌표를 출력해서 방문합니다.

while(!loc.empty()){
    x = loc.front().first;
    y = loc.front().second;
    loc.pop();

 

이후 

(x-1, y) , (x+1, y) , (x, y-1) , (x, y+1) 을 검사합니다. 만약 방문 가능하면 큐에 삽입하고, 거리를 계산해서 삽입합니다.

int x_dir[] = {-1, 1, 0, 0}; //상하
int y_dir[] = {0, 0, -1, 1}; //좌우

for (int i = 0; i < 4; i++){
        next_x = x + x_dir[i];
        next_y = y + y_dir[i];

        if( next_x >= 0 and next_x < N and next_y >=0 and next_y < M ){
            if(maze[next_x][next_y] == 1){
                maze[next_x][next_y] = maze[x][y] + 1;
                loc.push(make_pair(next_x,next_y));
            }
        }
    }

 

마지막으로 결과값을 출력합니다.

cout << maze[N-1][M-1] << endl;

 

C++백준 2178 번 미로 탐색 최종 코드입니다..

#include <iostream>
#include <queue>
#define MAX 101
using namespace std;
int maze[MAX][MAX] = {0,};

int main(){
    int N, M;
    string row;
    cin >> N >> M;
    for (int i = 0; i<N; i++){ //미로 입력
        cin >> row; //string으로 한번에 입력 받고
        for (int j = 0; j<M; j++){
            maze[i][j] = row[j] - '0'; //각 글자에 접근하여 숫자로 변환해서 maze에 입력
        }
    }


    queue<pair<int, int>> loc; //미로 안의 위치
    int x = 0, y = 0; //현재 위치 좌표값
    int next_x, next_y; //다음 위치 좌표값
    loc.push(make_pair(0,0));

    int x_dir[] = {-1, 1, 0, 0}; //상하
    int y_dir[] = {0, 0, -1, 1}; //좌우

    while(!loc.empty()){
        x = loc.front().first;
        y = loc.front().second;
        loc.pop();
        for (int i = 0; i < 4; i++){
            next_x = x + x_dir[i];
            next_y = y + y_dir[i];

            if( next_x >= 0 and next_x < N and next_y >=0 and next_y < M ){
                if(maze[next_x][next_y] == 1){
                    maze[next_x][next_y] = maze[x][y] + 1;
                    loc.push(make_pair(next_x,next_y));
                }
            }
        }
    }
    cout << maze[N-1][M-1] << endl;

    return 0;
}

 

C++ 백준 2178 번 미로 탐색 이었습니다.

감사합니다.