2178번

2178번 - 미로탐색

가장 간단한 BFS 구현 문제.

출발점에서 끝점까지 최소값을 구하는 것이고, 한점에서 다른 점으로 이동 비용이 1칸으로 동일하므로 BFS를 구현하여 최소값을 찾을 수 있다.

단, 이 문제에서 예제로 구한 답을 보면

시작점과 끝점을 모두 포함하기 때문에, dist 의 시작점 값이 0이 아니라 1로 초기화해서 문제를 풀었다.

입력으로 char 형을 받는건 앞에서 풀어본 문제와 동일하여 손쉽게 패쓰~

<정답 코드>

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1, -1, 0, 0 };
 
int N, M;
int map[101][101];
bool check[101][101];
int dist[101][101];
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char a;
            cin >> a;
            map[i][j] = a - '0';
        }
    }
 
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    check[0][0] = true;
    dist[0][0] = 1;
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M && !check[nx][ny] && map[nx][ny]==1)
            {
                q.push(make_pair(nx, ny));
                dist[nx][ny] = dist[x][y] + 1;
                check[nx][ny] = true;
            }
        }
    }
 
    cout << dist[N - 1][M - 1] << endl;
    
    return 0;
}