미로만들기 (feat. 백준, 2665번)

미로만들기
https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int N, arr[51][51]{0}, dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
bool visit[51][51]{false};
int bfs(register int x, register int y){
    register int cnt = 0;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
    visit[x][y] = true;
    q.push(make_tuple(cnt, x, y));
    while(!q.empty()){
        cnt = get<0>(q.top()), x = get<1>(q.top()), y = get<2>(q.top()); q.pop();
        if(x == N && y == N)
            break;
        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 <= N && !visit[nx][ny]){
                visit[nx][ny] = true;
                if(arr[nx][ny] == 0)
                    q.push(make_tuple(cnt + 1, nx, ny));
                else
                    q.push(make_tuple(cnt, nx, ny));
            }
        }
    }
    return cnt;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N;
    char v;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j){
            cin >> v;
            if(v == '1')
                arr[i][j] = 1;
            else
                arr[i][j] = 0;
        }
    cout << bfs(1, 1);
    return 0;
}
// *&)*@*

 

반응형

너비 우선 탐색 (bfs) 을 활용하는 문제입니다.

우선순위큐 (priority_queue) 를 활용하여 흰색 길로 가는 경우에 대해서 우선 탐색되도록 풀이하였습니다.