[백준] 2178 미로 탐색

문제 설명

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

2178번: 미로 탐색

 

N * M의 크기의 미로가 있을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소 칸의 수를 구하기

 

문제 풀이법

최단거리를 구하는 문제를 BFS를 사용하여 풀어야 한다

따라서, 큐를 사용하여 문제를 풀되, 이동할 때 지나야 하는 최소 칸의 수를 구하기 위해서 int visited[101][101] 배열을 활용한다

기본적인 BFS문제에서는 visited 배열에 방문했으면 1, 방문하지 않았으면 0을 입력하여서 방문 여부를 가렸는데, 이 문제에서는 최단 거리를 구하기 위해, visited 배열에 지금까지 지나온 거리를 입력해준다

입력하지 않았으면 -1, (1, 1) 위치에서 출발하였으므로 visitied[1][1]은 0으로 초기화 한 후, 만일 (y, x)에서 (ny, nx)로 이동한다면, visited[ny][nx] = visited[x] + 1을 해준다

 

소스 코드

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

int dy[4] = { 1, 0, -1, 0};
int dx[4] = { 0, 1, 0, -1};

int main()
{
    int n, m;
    int arr[101][101];
    int visited[101][101];
    
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = str[j] - '0';
            visited[i][j] = -1;
        }
    }
    
    queue<pair<int, int>> q;
    
    q.push({0, 0});
    visited[0][0] = 0;
    
    while(!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if (ny < 0 || nx < 0 || ny >= n || nx >= m || arr[ny][nx] == 0 || visited[ny][nx] >= 0)
                continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    printf("%d\n", visited[n - 1][m - 1] + 1);

    return 0;
}