백준 2178 미로 탐색

dfs는 길은 찾을 수 있지만, 최소 비용을 찾을 수는 없다.

bfs는 단계별로 주변으로 퍼져나가기 때문에 최소 비용문제를 풀 수 있다.

대신 가중치가 1이어야 한다.

 

visit 배열에 거리를 계속 더해서 저장한다. 한 칸 이동하는 것을 가중치가 1 증가하는 것으로 생각한다.

따라서 visit가 0일 때만 방문하고, 0이 아닐 경우 최소 비용이 갱신되지 않으므로 방문할 필요가 없다.

코드는 아래에..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int n, m;
int maze[100][100];
int visit[100][100];
 
int dr[4] = { -1, 0, 1,  0 };
int dc[4] = {  0, 1, 0, -1 };
 
void bfs() {
    queue<pair<int, int>> q;
 
    visit[0][0] = 1;
    q.push(make_pair(0, 0));
 
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
            //배열 안에 들어가는지 검사
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                //방문 했던 곳을 재방문하면 최소 비용이 갱신되지 않으므로 방문할 필요가 없다.
                //visit가 0일 때만 방문한다.
                if (visit[nr][nc] == 0 && maze[nr][nc] == 1) {
                    visit[nr][nc] = visit[row][col] + 1;
                    q.push(make_pair(nr, nc));
                }
            }
        }
    }
}
 
int main(int argc, char** argv) {
    int cnt = 0;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
 
    bfs();
    printf("%d\n", visit[n - 1][m - 1]);
 
    return 0;
}