백준 1430번 - 공격 (C++)

문제

해결 방법

BFS를 통하여 풀 수 있는 평범한 문제라고 생각한다. 적 위치부터 너비 기반 탐색을 시작하여며 탑을 발견하였다면  n번에 걸쳐서 발견한 탑인지에 따라 에너지/2^n를 누적해주어 탑끼리의 에너지 전달을 구현하였다.

BFS방식은 2차원 벡터를 통하여 3,0(Vec[3][0])을 기준으로 2거리 이내의 탑을 찾는다고 한다면, x를 기준으로 최대, 최소인 Vec[1] 부터 Vec[5]까지만 순회하며 해당 좌표가 두 점 사이의 공식(sqrt(pow(XX - i, 2) + pow(YY - j, 2)))을 통하여 거리가 2거리 이내인지 판별하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, R, D, X, Y, dummy1, dummy2;
    double Max = 0;
    vector<vector<int>> Graph(1001);
    queue<tuple<int, int, int>> BFS_Que;
    bool Visit[1000][1000] = {0, };
    cin >> N >> R >> D >> X >> Y;
 
    for (int i = 0; i < N; ++i)
    {
        cin >> dummy1 >> dummy2;
        Graph[dummy1].emplace_back(dummy2);
    }
    BFS_Que.emplace(X, Y, -1);
    Visit[X][Y] = true;
    while (!BFS_Que.empty())
    {
        int XX = get<0>(BFS_Que.front());
        int YY = get<1>(BFS_Que.front());
        int Count = get<2>(BFS_Que.front());
        BFS_Que.pop();
 
        for (int i = XX - R; i <= XX + R; ++i)
        {
            if (i < 0) i = 0;
            else if (i > 1000) break;
            for (auto j : Graph[i])
            {
                if (sqrt(pow(XX - i, 2) + pow(YY - j, 2)) <= R && !Visit[i][j])
                {
                    BFS_Que.emplace(i, j, Count+1);
                    Max += D/pow(2, Count+1);
                    Visit[i][j] = true;
                }
            }
        }
    }
 
    cout << Max;
}

 

잡설 :  이 문제도 내가 처음 포스팅 한 문제다 ㅎㅎ