[백준/C,C++] 2178번: 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

풀이

간단한 BFS 문제입니다.

 

이동 가능한 방향은 최대 4방향(상, 하, 좌, 우)이며,

 

BFS로 0을 제외한 모든 노드에 대해 깊이를 계산해 준 후에

 

(N, M)의 깊이를 출력해 주면 됩니다.

 

 

유의해야 할 점은 모든 노드에서 4방향(상, 하, 좌, 우)으로 이동할 수 있는 것은 아니기에

 

해당 방향으로 갈 수 있는지, 해당 방향의 노드가 갈 수 있는 지점(1이면 가능, 0이면 불가능)인지 체크하고,

 

방문했던 곳인지를 체크해주면 됩니다.

 

#include<iostream>
#include<queue>

using namespace std;

const int MAX = 100;

#define py first
#define px second

int n, m;
string maze[MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> q;
pair<int, int> d[4] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int res[MAX][MAX];

void visit(int y, int x)
{
    visited[y][x] = true;
    q.push(pair(y, x));
}

void BFS()
{
    visit(0, 0);

    while (!q.empty()) {
        pair<int, int> node = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = node.py + d[i].py;
            int nx = node.px + d[i].px;
            if (ny >= 0 && nx >= 0 && ny < n && nx < m) {
                if (!visited[ny][nx] && maze[ny][nx] != '0') {
                    visit(ny, nx);
                    res[ny][nx] = res[node.py][node.px] + 1;
                }
            }
        }
    }
}

int main(void)
{
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }

    BFS();

    if (n > 1 && m > 1) cout << res[n - 1][m - 1] + 1;

    return 0;
}

반례

Input

2 2

11

11

Output

3

 

Input

5 5
10011
11110
11001
11111
11101

Output

9