[2178] 미로 탐색

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

2178번: 미로 탐색

<문제>

bfs의 중요한 특성중 하나이자, dfs로는 못풀지만 bfs로 풀리는 문제가 존재하는 이유는

"먼저 도착하는것이 최적해"라는 특징이며, 이를 활용하는 문제라고 할수 있다.

 

매 정점마다 도착지점인지를 검사하고

도착지점이라면 바로 break하는것이 dfs보다 더 빠를 수 있는 가능성을 보여준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int y, x, turn;
} state;  //(y,x) <-> (R,C)
int Map[101][101], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int n, m;  // maxRow,maxColumn of map
void input(void) {
    cin >> n >> m;
    string temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        for (int j = 0; j < m; j++) {
            Map[i][j] = temp[j] - '0';  // string -> int
        }
    }
    return;
}
void bfs(int startY, int startX) {
    // init
    queue<state> q;
    q.push({startY, startX, 1});  // default turn is 1, including (1,1)
    bool visited[101][101];
    memset(visited, 0, sizeof(visited));
    visited[startY][startX] = true;
    // search
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        // check answer
        if (cur.y == n - 1 && cur.x == m - 1) {
            cout << cur.turn;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nextY = cur.y + dy[i];
            int nextX = cur.x + dx[i];
            if (nextY < 0 || nextX < 0 || startY >= n || startX >= m)
                continue;  // out of bound
            if (Map[nextY][nextX] == 1 && visited[nextY][nextX] == false) {
                q.push({nextY, nextX, cur.turn + 1});
                visited[nextY][nextX] = true;
            }
        }
    }
}
int main(void) {
    input();
    bfs(0, 0);
    return 0;
}