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

문제

바로가기

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

해결 방법

bfs, 큐, 구조체를 적절히 사용하면 빠르게 풀 수 있는 문제

bfs로 맵을 탐색할때마다 큐에 각 칸의 정보를 저장해줘야 하는데, 

<x좌표, y좌표, 현재 칸 까지의 최소 거리> 형식으로 저장해주면 된다!

예를 들어, n = 4, m = 6이고 

맵이 아래와 같이 주어진 경우, 

110110
110110
111111
111101

 

큐에 담기는 순서는 아래와 같다.

(0, 0, 1)

(0, 1, 2)

(1, 0, 2)

(1, 1, 3)

(2, 0 3)

(2, 1, 4)

(3, 0, 4)

(2, 2, 5)

(3, 1, 5)

(2, 3, 6)

(3, 2, 6)

(1, 3, 7)

(2, 4, 7)

(3, 3, 7)

(0, 3, 8)

(1, 4, 8)

(2, 5, 8)

(0, 4, 9)

(3, 5, 9) -> 도작점이므로 여기서 9를 출력하고 프로그램 종료!

 

 

내 코드

// [2178] 미로 탐색
// bfs
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

char map[101][101];
bool visited[101][101];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct MazeInfo {
    int x;
    int y;
    int dis;
};

int solution(int n, int m)
{
    int ans = 1, x, y, dis;
    queue<MazeInfo> q;
    MazeInfo info = {0, 0, 1};
    q.push(info);
    visited[0][0] = true;

    while(!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        dis = q.front().dis;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }
            if(map[nx][ny] == '0' || visited[nx][ny] == true) {
                continue;
            }
            if(nx == n-1 && ny == m-1) {
                return dis + 1;
            }
            MazeInfo info = {nx, ny, dis + 1};
            q.push(info);
            visited[nx][ny] = true;
        }
    }
}

int main(void)
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> map[i];
    }
    cout << solution(n, m) << '\n';
}