[Queue/Deque] 큐/덱 - BFS 미로찾기

BFS for Maze

N × M크기의 배열로 표현되는 미로가 있다. 미로에서 0은 이동할 수 있는 칸을 나타내고, 1은 이동할 수 없는 칸을 나타낸다. S는 출발점을 의미하며 T는 도착점을 의미한다.

이러한 미로가 주어졌을때 BFS를 수행하여 출발점에서 도착점으로 이동하는 최단 경로의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 칸의 수를 셀 때는 S와 T도 포함한다.

Input

첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 50)이 주어진다.

다음 N개의 줄에는 M개의 문자로 미로가 주어진다. 각각의 문자들은 붙어서 입력으로 주어진다.

Output

첫째 줄에 BFS를 통해 지나야 하는 최단 경로의 칸 수를 출력한다. 도착점에 도달할 수 없는 경우는 0을 출력한다.

Sample Input 1

4 6

1S1000

101010

100010

11100T

Sample Output 1

8

Sample Input 2

4 6

1S1000

101011

100010

11101T

Sample Output 2

0

Sample Input 3

5 6

110S11

100001

101101

100001

111T11

Sample Output 3

7

 

정답1 (정석 BFS 풀이 이용)

#include <iostream>
#include <queue>
#define MAX 51

using namespace std;

int N, M;                       // 미로 크기
int maze[MAX][MAX];             // 미로 표현용 2차원 배열
int visited[MAX][MAX];          // 방문 기록용 2차원 배열
int dist[MAX][MAX];             // 이동칸 기록용 2차원 배열

int x_dir[4] = {-1, 1, 0, 0};   // 상화좌우 x축 방향
int y_dir[4] = {0, 0, -1, 1};   // 상화좌우 y축 방향

queue<pair<char,char>> q;        // 탐색 좌표 저장용 queue

// 미로 경로 탐색
void bfs(int start_x, int start_y){         
    visited[start_x][start_y] = 1;          // 입력 받은 시작 좌표를 방문
    q.push(make_pair(start_x,start_y));     // queue 에 삽입
    dist[start_x][start_y]++;               // 시작 좌표까지 이동한 칸을 1로 지정

    // 모든 좌표를 탐색할 때까지 반복
    while (!q.empty()){
        // queue 의 front 좌표를, 현재 좌표로 지정
        int x = q.front().first;
        int y = q.front().second;

        // qeueu 의 front 좌표 제거
        q.pop();

        // 현재 좌표와 상하좌우로 인접한 좌표 확인
        for (int i=0; i<4; ++i){
            // 현재 좌표와 상하좌우로 인접한 좌표
            int x_new = x + x_dir[i];
            int y_new = y + y_dir[i];
            // 인접한 좌표가, 미로 내에 존재하는지, 방문한 적이 없는지, 이동이 가능한지 확인
            if ( (0 <= x_new && x_new < N) && (0 <= y_new && y_new < M) 
            && !visited[x_new][y_new] && (maze[x_new][y_new] == '0'  || maze[x_new][y_new] == 'T')){
                visited[x_new][y_new] = 1;              // 인접 좌표는 방문한 것으로 저장
                q.push(make_pair(x_new, y_new));        // 인접 좌표를 queue 에 삽입
                dist[x_new][y_new] = dist[x][y] + 1;    // 인접 좌표까지 이동한 거리 저장
            }
        }
    }
}

int main(){
    int aa, bb;
    int a,b;
    cin >> N >> M;                      // 미로 크기 입력

    for (int i=0; i<N; ++i){            // 미로 입력

        string row;                     // 행 입력
        cin >> row;

        for (int j=0; j<M; ++j){        // 행 별 좌표값 저장
            maze[i][j] = row[j];    // 행 별 좌표값들은 문자 형태이기 때문에, 숫자로 변환
            if(maze[i][j]=='S'){
                a = i;
                b = j;
            }
            else if(maze[i][j]=='T'){
                aa = i;
                bb = j;
            }
        }
    }

    bfs(a, b);                       // 미로 탐색 시작

    cout << dist[aa][bb] <<endl;             // 도착 좌표까지의 거리 출력
}

 

정답2(직접 클래스 구현):

#include <deque>
#include <stack>
#include <iostream>

using namespace std;

struct Location2D {
    int row;    //현재위치의 행번호
    int col;    // 현재위치의 열번호
    Location2D(int r = 0, int c = 0) { row = r; col = c; } 

    bool isNeighbor(Location2D& p) {  //위치 p가 자신의 이웃인지 검사하는 함수
        return ((row == p.row && (col == p.col - 1 || col == p.col + 1)) || (col == p.col && (row == p.row - 1 || row == p.row + 1)));
    }
    //위치 p가 자신과 같은 위치인지를 검사하는 함수(연산자 오버로딩 사용)
    bool operator ==(Location2D& p) { return row == p.row && col == p.col; }
};


//(r,c)가 갈 수 있는 위치인지를 검사
//(r,c)가 배열 안에 있고, 값이 갈 수 있는 위치 '0'이거나 출구 'T'이어야함


int main() {
    deque<Location2D> locDeque; //위치 큐 객체 생성
    int N, M, cnt = 1; 
    char map[50][50];
    int count[50][50] = { 0 }; // 좌표의 거리값을 저장하는 수단
    cin >> N >> M;
    

    for (int a = 0; a < N; a++) { // 미로 생성 및 입구 객체 생성
        for (int b = 0; b < M; b++) {
            cin >> map[a][b];
            if (map[a][b] == 'S') {
                Location2D entry(a, b); // 입구 객체
                count[a][b] = cnt;
                locDeque.push_back(entry);
            }
        }
    }

    while (!locDeque.empty()) { //큐가 비어있지 않는 동안
        Location2D here = locDeque.front(); //큐의 front 상단 객체 복사
        locDeque.pop_front(); //큐의 상단 객체 삭제;

        int r = here.row;
        int c = here.col;

        if (map[r][c] == 'T') {    // 출구를 만났으면 -> 탐색 성공
            printf("%d\n",count[r][c]);
            return 0;
        }

        else {      //출구가 아니면
            if ((r - 1 >= 0 && c >= 0 && r - 1 < N && c < M) && ((map[r - 1][c] == '0' || map[r - 1][c] == 'T')) && (count[r - 1][c] == 0)) {
                locDeque.push_back(Location2D(r - 1, c));
                count[r-1][c] = count[r][c] + 1;
            }
            if ((r + 1 >= 0 && c >= 0 && r + 1 < N && c < M) && ((map[r + 1][c] == '0' || map[r + 1][c] == 'T')) && (count[r + 1][c] == 0)) {
                locDeque.push_back(Location2D(r + 1, c));
                count[r + 1][c] = count[r][c] + 1;
            }
            if ((r >= 0 && c - 1 >= 0 && r < N && c - 1< M) && ((map[r][c - 1] == '0' || map[r][c - 1] == 'T')) && (count[r][c - 1] == 0)){
                locDeque.push_back(Location2D(r, c -  1));
                count[r][c-1] = count[r][c] + 1;
            }
            if ((r >= 0 && c + 1 >= 0 && r < N && c + 1< M) && ((map[r][c + 1] == '0' || map[r][c + 1] == 'T')) && (count[r][c + 1] == 0)) {
                locDeque.push_back(Location2D(r, c + 1));
                count[r][c+1] = count[r][c] + 1;
            }
        }

    }

    printf("0\n");

    
    return 0;
}