쉬운 최단거리 (feat. 백준, 14940번)

쉬운 최단거리
https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int ans[1001][1001]{0}, dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
bool arr[1001][1001]{false};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int n, m, sx, sy;
    cin >> n >> m;
    for(register int i = 1, j, v; i <= n; ++i)
        for(j = 1; j <= m; ++j){
            cin >> v;
            if(v == 2)
                sx = i, sy = j;
            else if(v == 1)
                arr[i][j] = true, ans[i][j] = -1;
        }
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(sx, sy, ans[sx][sy]));
    while(!q.empty()){
        auto x = get<0>(q.front()), y = get<1>(q.front()), cost = get<2>(q.front()); q.pop();
        for(register int d = 0, nx, ny; d < 4; ++d){
            nx = x + dx[d], ny = y + dy[d];
            if(1 <= nx && nx <= n && 1 <= ny && ny <= m && arr[nx][ny] && ans[nx][ny] == -1)
                ans[nx][ny] = cost + 1, q.push(make_tuple(nx, ny, cost + 1));
        }
    }
    for(register int i = 1, j, v; i <= n; ++i){
        for(j = 1; j <= m; ++j)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
	return 0;
}
// *&)*@*

 

반응형

오랜만에 탐색 문제를 풀었습니다.

해당 문제는 너비 우선 탐색(bfs) 으로 풀이하였으나 깊이 우선 탐색(dfs) 로도 충분히 풀이가 가능합니다.

갈 수 있었는데 실제로는 못 간 구역을 -1 로 출력하는 것이 핵심입니다.