[백준] 2178 미로탐색(C++)

문제 URL

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

2178번: 미로 탐색

[문제 설명]

다음 문제는 N×M크기의 배열로 표현되는 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하는 문제이다. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

주어진 미로

 

[문제 풀이]

 

BFS를 사용하여 푸는 문제이다. 
(1,1)에서 (N,M)까지 가는 최단 경로를 출력하면 된다.
현재 칸에서 갈 수 있는 다음 칸에 +1을 하여 거리를 세어준다.

입력이 빈칸없이 주어져서 string으로 받은 다음에 반복문을 사용하여 int로 한 칸씩 잘라서 넣어줘야한다.

---

#include <iostream>
#include <queue>
#define MAX 101
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<int,int> > 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] == 1 ){
                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(){
    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]-'0';    // 행 별 좌표값들은 문자 형태이기 때문에, 숫자로 변환
        }
    }

    bfs(0, 0);                          // 미로 탐색 시작
    cout << dist[N-1][M-1];             // 도착 좌표까지의 거리 출력
}

참고: https://onony.tistory.com/95