[백준] 2178 미로탐색

 

풀이

문제를 그래프로 생각해보자. 미로의 각 칸을 정점으로 보고, 상/하/좌/우로 이동 가능한 칸 끼리는 간선으로 연결된 그래프라고 생각했을 때 최단 이동 횟수는 간선 가중치가 전부 1인 그래프 최단거리임을 알 수 있다. 이를 통해 이 문제는 BFS로 해결하면 되겠구나! 하는 아이디어를 떠올리면된다. 사실 BFS로 풀면되겠다는 아이디어만 떠올리면 BFS의 전형적인 그 코드 흐름을 따라 구현하기만 하면되기때문에 BFS 문제중에서 난이도가 낮은편인 문제라 생각한다. (그렇다고 막 쉽진 않지만...)

#include <bits/stdc++.h>
using namespace std;

string board[102];
int dist[102][102];
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> board[i];
    for (int i = 0; i < n; i++) fill(dist[i], dist[i] + m, -1);

    queue<pair<int,int>> q;
    q.push({0,0});
    dist[0][0] = 0; 

    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny] >= 0 || board[nx][ny] != '1') continue; 

            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            q.push({nx,ny});
        }
    }

    cout << dist[n-1][m-1] + 1;
    return 0;
}

 

마지막 출력에서 +1을 해주는이유는 시작칸을 포함해서 몇칸을 밟고 최소의 횟수로 목표에 도착했는지를 묻고있기 때문에 
이동횟수 + 1을 하여 밟은 칸 수를 구하였다.