2585 경비행기 (자바스크립트)

문제

경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간에 내려서 급유를 받는 횟수가 적은 장점이 있지만 연료통의 무게로 인하여 속도가 느려지고, 안정성에도 문제가 있을 수 있다. 한편 작은 연료통을 장착하면 비행기의 속도가 빨라지는 장점이 있지만 중간에 내려서 급유를 받아야 하는 횟수가 많아지는 단점이 있다. 문제는 중간에 내려서 급유를 받는 횟수가 k이하 일 때 연료통의 최소용량을 구하는 것이다. 아래 예를 보자.

위 그림은 S, T와 7개의 중간 비행장의 위치를 나타내고 있는 그림이다. 위 예제에서 중간급유를 위한 착륙 허용 최대횟수 k=2라면 S-a-b-T로 가는 항로가 S-p-q-T로 가는 항로 보다 연료통이 작게 된다. 왜냐하면, S-p-q-T항로에서 q-T의 길이가 매우 길어서 이 구간을 위해서 상당히 큰 연료통이 필요하기 때문이다. 문제는 이와 같이 중간에 최대 K번 내려서 갈 수 있을 때 최소 연료통의 크기가 얼마인지를 결정하여 출력하면 된다. 참고사항은 다음과 같다.

1. 모든 비행기는 두 지점 사이를 반드시 직선으로 날아간다. 거리의 단위는 ㎞이고 연료의 단위는 ℓ(리터)이다. 1ℓ당 비행거리는 10㎞이고 연료주입은 ℓ단위로 한다.
2. 두 위치간의 거리는 평면상의 거리이다. 예를 들면, 두 점 g=(2,1)와 h=(37,43)간의 거리 d(g,h)는 (2−37)2+(1−43)2\(\sqrt{(2-37)^2 + (1-43)^2}\) = 54.671... 이고 50＜d(g,h) ≤ 60이므로 필요한 연료는 6ℓ가 된다.
3. 출발지 S의 좌표는 항상 (0,0)이고 목적지 T의 좌표는 (10000,10000)으로 모든 입력 데이터에서 고정되어 있다.
4. 출발지와 목적지를 제외한 비행장의 수 n은 3 ≤ n ≤ 1000이고 그 좌표 값 (x,y)의 범위는 0＜x,y＜10000의 정수이다. 그리고 최대 허용 중간급유 횟수 k는 0 ≤ k ≤ 1000이다.

 

====

문제 풀이

출발 지점은 (0,0), 도착 지점은(10_000,10_000)으로 고정되어 있는 문제이다.

특정 용량통을 가지고 출발 지점에서부터 도착 지점에 도착할 수 있는지를 문제이고 이 용량통의 최솟값을 알아내기 위해선 이분 탐색을 활용하였다.

const binary = (start, end) => {
    let s = start;
    let e = end;
    let answer = 0;

    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        const isSuccess = bfs(mid);
        if (isSuccess) {
            e = mid - 1;
            answer = mid;
        } else {
            s = mid + 1;
        }
    }
    return answer;
};

우선 각 좌표 간 이동을 위해 필요한 용량을 gr 배열에 기록해둔다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const arr = [
    [0, 0],
    ...input.slice(1).map((s) => s.split(' ').map(Number)),
    [10000, 10000],
];

const gr = Array.from({ length: n + 2 }, () => []);

for (let i = 0; i < n + 1; i++) {
    for (let j = i + 1; j < n + 2; j++) {
        const dis =
            ((arr[i][0] - arr[j][0]) ** 2 + (arr[i][1] - arr[j][1]) ** 2) **
            0.5;
        value = Math.ceil(dis / 10);
        gr[i].push([value, j]);
        gr[j].push([value, i]);
    }
}

용량의 특정 값 을 기준으로 탐색을 시작하는데, 현재에서 다음으로 이동하지 못하는 경우들을 생각해본다.

1. 현재 용량통이 이동을 위해 필요한 용량보다 작은 경우

2. 남은 오일이 이동을 위해 필요한 용량보다 작아서 재충전을 해야하는데 충전 횟수를 초과한 경우

3. 다음 노드에 방문 한 배열에는 재충전의 횟수를 기록할건데 지금의 탐색에 사용된 재충전의 횟수가 그 이상일 경우

const bfs = (volume) => {
    const visited = Array.from({ length: n + 2 }, () => Infinity);
    visited[0] = 0;
    const q = [[volume, 0, 0]];

    while (q.length) {
        const [restOil, curNode, dischargeCount] = q.shift();
        if (curNode === n + 1) return true;

        for (const [needOil, nextNode] of gr[curNode]) {
            if (needOil > volume) continue;
            if (needOil > restOil) {
                if (dischargeCount === m) continue;
                if (visited[nextNode] <= dischargeCount + 1) continue;
                visited[nextNode] = dischargeCount + 1;
                q.push([volume, nextNode, dischargeCount + 1]);
            } else {
                if (visited[nextNode] <= dischargeCount) continue;
                visited[nextNode] = dischargeCount;
                q.push([restOil - needOil, nextNode, dischargeCount]);
            }
        }
    }
    return false;
};

 

정답 코드

binary를 호출할 때 end가 1415로 고정된 이유는 0,0 에서 10_000,10_000 까지 필요한 용량이 1415 로 최댓값이기 때문이다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const arr = [
    [0, 0],
    ...input.slice(1).map((s) => s.split(' ').map(Number)),
    [10000, 10000],
];

const gr = Array.from({ length: n + 2 }, () => []);

for (let i = 0; i < n + 1; i++) {
    for (let j = i + 1; j < n + 2; j++) {
        const dis =
            ((arr[i][0] - arr[j][0]) ** 2 + (arr[i][1] - arr[j][1]) ** 2) **
            0.5;
        value = Math.ceil(dis / 10);
        gr[i].push([value, j]);
        gr[j].push([value, i]);
    }
}

const bfs = (volume) => {
    const visited = Array.from({ length: n + 2 }, () => Infinity);
    visited[0] = 0;
    const q = [[volume, 0, 0]];

    while (q.length) {
        const [restOil, curNode, dischargeCount] = q.shift();
        if (curNode === n + 1) return true;

        for (const [needOil, nextNode] of gr[curNode]) {
            if (needOil > volume) continue;
            if (needOil > restOil) {
                if (dischargeCount === m) continue;
                if (visited[nextNode] <= dischargeCount + 1) continue;
                visited[nextNode] = dischargeCount + 1;
                q.push([volume, nextNode, dischargeCount + 1]);
            } else {
                if (visited[nextNode] <= dischargeCount) continue;
                visited[nextNode] = dischargeCount;
                q.push([restOil - needOil, nextNode, dischargeCount]);
            }
        }
    }
    return false;
};
const binary = (start, end) => {
    let s = start;
    let e = end;
    let answer = 0;

    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        const isSuccess = bfs(mid);
        if (isSuccess) {
            e = mid - 1;
            answer = mid;
        } else {
            s = mid + 1;
        }
    }
    return answer;
};

const answer = binary(0, 1415);
console.log(answer);