Gorani Command (feat. 백준, 27445번)

Gorani Command
https://www.acmicpc.net/problem/27445

27445번: Gorani Command

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>
using namespace std;
int N, M, dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1}, ans[50][50];
void bfs(register int x, register int y, register int c){
    bool visit[50][50]{false};
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(x, y, c));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        x = get<0>(p), y = get<1>(p), c = get<2>(p);
        if(c == 0){
            ++ans[x][y];
            continue;
        }
        for(register int d = 0, ix, iy; d < 4; ++d){
            ix = x + dx[d], iy = y + dy[d];
            if(0 <= ix && ix < N && 0 <= iy && iy < M && !visit[ix][iy])
                visit[ix][iy] = true, q.push(make_tuple(ix, iy, c - 1));
        }
    }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(ans, 0, sizeof(ans));
    cin >> N >> M;
    for(register int n = 0, v; n < N; ++n)
        cin >> v, bfs(n, 0, v);
    for(register int m = 1, v; m < M; ++m)
        cin >> v, bfs(N - 1, m, v);
    register int x, y, v = 0;
    for(register int n = 0, m; n < N; ++n)
        for(m = 0; m < M; ++m)
            if(ans[n][m] > v)
                v = ans[n][m], x = n + 1, y = m + 1;
    cout << x << " " << y;
	return 0;
}
// *&)*@*

 

반응형

입력으로 주어진 거리만큼 갈수 있는 칸에 대해서 모두 체크 하였을때, 가장 많이 체크된 곳이 고라니가 있는 곳입니다.

따라서 위 내용을 bfs 로 구현하여 풀이하였습니다.