[Algorithm] Baekjoon 2585번 : 경비행기

https://www.acmicpc.net/problem/2585

2585번: 경비행기

struct Node
{
    int y;
    int x;
    int count = 0;
};
 
int convertLiter(int y2, int x2, int y1, int x1) 
{
    int distance = (int)ceil(sqrt(pow(y2 - y1, 2) + pow(x2 - x1, 2)));
    
    if (distance % 10 == 0) return distance / 10;
    else return distance / 10 + 1;
}
 
int n, k;
vector<Node> nodes;
bool visited[1001] = { false };
 
bool BFS(int standardLiter)
{
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    q.push({ 0,0,k });
    
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curCount = q.front().count;
        q.pop();
 
        int liter = convertLiter(curY, curX, 10000, 10000);
 
        if (liter <= standardLiter)
        {
            return true;
        }
 
        if (curCount == 0) continue;
 
        for (int i = 0; i < n; ++i)
        {
            if (visited[i]) continue;
 
            int nextY = nodes[i].y;
            int nextX = nodes[i].x;
            int liter = convertLiter(curY, curX, nextY, nextX);
 
            if (liter <= standardLiter)
            {
                visited[i] = true;
                q.push({ nextY,nextX,curCount - 1 });
            }
        }
    }
 
    return false;
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k;
 
    for (int i = 0; i < n; ++i)
    {
        int y, x;
        cin >> x >> y;
 
        nodes.push_back({ y,x });
    }
 
    int left = 0;
    int right = 10000000;
    int answer = 0;
    
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (BFS(mid))
        {
            answer = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
 
    return 0;
}

이전에 풀었던 결정문제와 같은 유형의 문제이다.

주어진 조건을 완전탐색으로하려면 당연히 시간초과가 걸리기 때문에, 아예 허용가능한 기름량을 이분탐색으로 조절해가며 해당 기름량으로 목적지까지 갈수있는지에 대해 Yes or No를 구한다.