24042 횡단보도 (자바스크립트)

문제

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 N$N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, 간접적으로 연결되어 있다. 편의상 N$N$ 개의 지역을 1$1$부터 N$N$까지로 번호를 붙이자.

당신은 이미 멀리서 교차로의 신호를 분석했기 때문에 횡단보도에 파란불이 들어오는 순서를 알고 있다. 횡단보도의 주기는 총 M$M$ 분이며 1$1$분마다 신호가 바뀐다. 각 주기의 1+i(0≤i<M)$1+i (0 \le i < M)$ 번째 신호는 i,M+i,2M+i,3M+i,⋯$i, M+i, 2M+i, 3M+i, \cdots$ 분에 시작해서 1$1$분 동안 Ai$A_i$번 지역과 Bi$B_i$번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도에 파란불이 들어오면 당신은 해당 횡단보도를 이용하여 반대편 지역으로 이동할 수 있으며 이동하는 데 1$1$분이 걸린다. 횡단보도를 건너는 도중에 신호가 빨간불이 되면 안되기 때문에 신호가 s∼e$s \sim e$ 시간에 들어온다면 반드시 s∼e−1$s \sim e-1$ 시간에 횡단보도를 건너기 시작해야 한다.

횡단보도와 신호의 정보가 주어질 때, 시간 0$0$분 에서 시작해서 1$1$번 지역에서 N$N$번 지역까지 가는 최소 시간을 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 지역의 수 N$N$, 횡단보도의 주기 M$M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 M$M$ 개의 줄 중 1+i$1+i$ 번째 줄에는 i,M+i,2M+i,3M+i,⋯$i, M+i, 2M+i, 3M+i, \cdots$ 분에 시작해서 1$1$분동안 파란불이 들어오는 횡단보도의 두 끝점 Ai$A_i$, Bi$B_i$가 공백으로 주어진다.

출력

첫 번째 줄에 1$1$ 번 지역에서 N$N$ 번 지역까지 가는데 필요한 최소 시간을 분단위로 출력한다.

 

====

문제 풀이

출발 지점인 1부터 시작하여 최대한 빠른 시간 안에 N에 도착하는 경우를 구하면 되는 문제이다.

가중치를 통해 최단 경로를 구하는 다익스트라 문제에서 횡단보도가 파란 불이 되는 시간으로 변경된 것으로 풀이를 해나갔다.

최소힙에서 우선순위를 나누는 요소는 현재까지의 시간이다.

1번부터 출발하여 갈 수 있는 경로들에서 횡단보도가 열리는 시간이 지금의 시간보다 더 크다면 그 시간까지 무조건 기다린 다음 건널 수 있다. 지금의 시간이 0초인데 갈 수 있는 경로들의 횡단보도가 3초, 5초에 열린다면 그 횡단보도는 3초, 5초까지 기다린 뒤 1초 동안 이동.

그럼 도착한 행단보도에는 3+1, 5+1 인 4초 6초가 기록된다. 이때 visited를 선언하여 그 경로에 그 전 시간으로 방문한 기록이 있다면 굳이 또 가게 되는 중복이므로 배제한다.

if (currentTime <= startTime) {
    if (visited[destiny] <= startTime + 1) continue;
    visited[destiny] = startTime + 1;
    q.push([startTime + 1, destiny]);

만약 현재의 시간이 횡단보도보다 크다면 그 횡단보도가 열리는 주기를 기다렸다가 시간이 되면 건너면 된다.

이것은 지금 시간이 10초인데 횡단보도가 3,5초에 열리고 주기가 5초라면

3+5, 3+10, 3+15,.... 중 10초보다 가장 가깝게 큰 3+10초까지 기다린 뒤 1초동안 이동하여 14초

5+5, 5+10, 5+15,... 중 10초보다 가장 가깝게 큰 10초에 1초동안 이동하여 11초에 도착

이 주기를 맞추는 것은 (현재 시간 - 초기 시간)/주기 에서 올림수 하면 몇 번의 주기인지 맞출 수 있다.

} else {
    let idx = Math.ceil((currentTime - startTime) / m);

    const time = idx * m + startTime;
    if (visited[destiny] <= time + 1) continue;
    visited[destiny] = time + 1;
    q.push([time + 1, destiny]);
}

이제 최종적으로 visited[n]을 출력하면 이것이 최단 시간이 되어 정답이 됨.

정답 코드

class MinHeapq {
    #heapq;
    constructor() {
        this.#heapq = [undefined];
    }
    print() {
        console.log(this.#heapq);
    }
    isEmpty() {
        return this.#heapq.length === 1;
    }
    getSize() {
        return this.#heapq.length;
    }
    swap(target, destiny) {
        [this.#heapq[target], this.#heapq[destiny]] = [
            this.#heapq[destiny],
            this.#heapq[target],
        ];
    }
    #upLevel() {
        let cur = this.getSize() - 1;

        while (cur > 1) {
            let parent = Math.floor(cur / 2);
            if (this.#heapq[parent][0] <= this.#heapq[cur][0]) break;
            this.swap(cur, parent);
            cur = parent;
        }
    }
    #downLevel() {
        let cur = 1;
        while (cur < this.getSize()) {
            let smallest = cur * 2;
            if (smallest >= this.getSize()) break;
            const right = smallest + 1;
            if (right < this.getSize()) {
                smallest =
                    this.#heapq[smallest][0] > this.#heapq[right][0]
                        ? right
                        : smallest;
            }

            if (this.#heapq[cur][0] > this.#heapq[smallest][0]) {
                this.swap(cur, smallest);
                cur = smallest;
            } else {
                break;
            }
        }
    }
    push(arr) {
        this.#heapq.push(arr);

        this.#upLevel();
    }
    pop() {
        if (this.isEmpty()) return undefined;
        const returnArray = this.#heapq[1];
        const lastArray = this.#heapq.pop();
        if (this.isEmpty()) return lastArray;
        this.#heapq[1] = lastArray;
        this.#downLevel();

        return returnArray;
    }
}

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 = input.slice(1).map((s) => s.split(' ').map(Number));

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

for (let startTime = 0; startTime < m; startTime++) {
    const [s, e] = arr[startTime];
    gr[s].push({
        destiny: e,
        startTime,
    });
    gr[e].push({
        destiny: s,
        startTime,
    });
}

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

const q = new MinHeapq();
q.push([0, 1]);

while (!q.isEmpty()) {
    const [currentTime, currentPosition] = q.pop();
    for (const { destiny, startTime } of gr[currentPosition]) {
        if (currentTime <= startTime) {
            if (visited[destiny] <= startTime + 1) continue;
            visited[destiny] = startTime + 1;
            q.push([startTime + 1, destiny]);
        } else {
            let idx = Math.ceil((currentTime - startTime) / m);

            const time = idx * m + startTime;
            if (visited[destiny] <= time + 1) continue;
            visited[destiny] = time + 1;
            q.push([time + 1, destiny]);
        }
    }
}

console.log(visited[n]);

,

 

 

클래스 MinHeapq {
#HeAPQ;
생성자 () {
이것은#heapq = [undefined];
}
getheapq () {
Console.log (this.#heapq);
}
isempty () {
이것을 반환합니다.#heapq.length === 1;
}
getsize () {
이것을 반환하십시오.#heapq.length;
}
스왑 (Target, Destiny) {
[this.#HeaPQ [대상], this.#HeaPQ [Destiny]] = [
#heapq [Destiny],
#heapq [대상],
];
}
#uplevel () {
cur = this.getsize () -1을 let let let.

while (cur> 1) {
Parent = Math.floor (cur / 2);
if (this.#heapq [parent] [0] <= this.#heapq [cur] [0]) break;
this.swap (cur, parent);
cur = 부모;
}
}
#downlevel () {
cur = 1을하자;
while (cur <this.getsize ()) {
가장 작은 = cur * 2;
if (smallest> = this.getSize ()) break;
const right = 가장 작은 + 1;
if (right <this.getsize ()) {
가장 작은 =
#heapq [가장 작은] [0]> this.#heapq [오른쪽] [0]
? 오른쪽
: 가장 작은;
}

if (this.#heapq [cur] [0]> this.#heapq [가장 작은] [0]) {
this.swap (cur, smallest);
cur = 가장 작은;
} 또 다른 {
부서지다;
}
}
}
푸시 (arr) {
#heapq.push (ARR);

#uplevel ();
}
팝() {
if (this.isempty ())를 정의하지 않은 반환;
const returnArray = this.#heapq [1];
const lastarray = this.#heapq.pop ();
if (this.isempty ()) return lastArray;
#heapq [1] = lastArray;
이.#downlevel ();

반환 returnArray;
}
}

const input = require ( 'fs')
.readfilesync (process.platform === 'linux'? '/dev/stdin': './input.txt')
.TOSTRING ()
.손질()
.split ( '\ n');

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

const gr = array.from ({길이 : n + 1}, () => []);

for (starttime = 0; starttime <m; starttime ++) {
const [s, e] = arr [starttime];
gr [s] .push ({
운명 : E,
시작 시간,
});
gr [e] .push ({
운명 : S,
시작 시간,
});
}

const visited = array.from ({길이 : n + 1}, () => infinity);
방문 [1] = 0;

const q = New Minheapq ();
Q.push ([0, 1]);

while (! q.isempty ()) {
const [currenttime, currentPosition] = q.pop ();
for (const {destiny, starttime}의 gr [currentPosition]) {
if (currenttime <= starttime) {
(방문한 [Destiny] <= starttime + 1) 계속;
방문 [Destiny] = startTime + 1;
Q.push ([StartTime + 1, Destiny]);
} 또 다른 {
idx = math.ceil ((currenttime -starttime) / m하자;

const time = idx * m + starttime;
(방문한 [Destiny] <= time + 1) 계속;
방문 [Destiny] = Time + 1;
Q.push ([Time + 1, Destiny]);
}
}
}

Console.log (방문 [n]);