미로 탐색 2178

문제

접근 방법

프로그래머스의 게임 맵 최단거리와 유사한 문제이다. 차이점은 배열을 받는 방법의 차이인 것 같다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M));
    queue<pair<int, int>> bfs;
    for (int i = 0; i < N; ++i)
    {
        string k;
        cin >> k;
        for (int j = 0; j < M; ++j)
        {
            map[i][j] = k[j] - '0';
        }
    }
    bfs.push({0, 0});
    while (!bfs.empty())
    {
        auto cur = bfs.front();
        bfs.pop();
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
            if (next.first < 0 || next.second < 0 || next.first >= N || next.second >= M)
                continue;
            if (!map[next.first][next.second] || map[next.first][next.second] > 1)
                continue;
            map[next.first][next.second] = map[cur.first][cur.second] + 1;
            bfs.push(next);
        }
    }
    cout << map[N - 1][M - 1];
    return 0;
}

풀이

게임 맵 최단거리와 같은 방법으로 해결하면 된다.
이번 문제를 풀면서 생각해보니 0, 0의 위치는 계속 1이기에 map[next.first][next.second] > 1에 걸리지 않아 다시 돌아갈 수 있다. 하지만 다른 위치는 모두 1 이상이기에 무한 반복되는 문제는 발생하지 않는다.