글 읽기 - javascript 5719 거의 최단 경로 33%에서 시간 초과..

yeum0523 2년 전 0

안녕하세요! 5719 최단 경로 문제를 풀고 있는데..

계속 33%에서 시간 초과가 나버리네요...

이 문제를 디악스트라 1번 해서 구해진 최단 경로를 bfs로 없애주고, 다시 디악스트라를 통해 거의 최단 거리를 구하는 로직으로 구현하였습니다.

나름대로 최대한 줄여본다고 했는데.. 어디에서 시간 초과가 나는지 잘 모르겠네요..

꼭 조언 받고 싶습니다!!!!!!!

const [...data] = require('fs').readFileSync(__dirname + '/example.txt').toString().trim().split('\n');
let curIdx = 0;

function dijkstra(start, graph, distance) {
    const queue = [];
    queue.push([0, start]);
    distance[start] = 0;
    while (queue.length > 0) {
        const [dist, now] = queue.shift();
        if (dist > distance[now]) continue;
        for (let i = 0, length = graph[now].length; i < length; i++) {
            const [curDist, curNode] = graph[now][i];
            const cost = dist + curDist;
			// 끊어진 간선이 아니거나, 방금 구한 최단 거리가 기존의 최단 거리보다 크다면..
            if (!(curDist === -1) && cost < distance[curNode]) {
                distance[curNode] = cost;
                queue.push([cost, curNode]);
                queue.sort((a, b) => a[0] - b[0]);
            }
        }
    }
}

function bfs(end, graph, reversedGraph, distance) {
    const [visit, needVisit] = [Array(graph.length).fill(false), [end]];
    visit[end] = true;
    while (needVisit.length > 0) {
        const node = needVisit.shift();
        for (let i = 0; i < reversedGraph[node].length; i++) {
            const [curCost, curNode, length] = reversedGraph[node][i];
			// 방문 하지 않는 노드에, 이전의 경로라면..
			// 예를 들어, 4(현재 최단 경로) === 3(현재 노드의 비용) + 1 (현재 노드와 연결된 간선의 비용) 
			// 이를 통해 현제 노드까지 오는데 이전의 노드를 알 수 있음.
            if (!visit[curNode] && distance[node] === distance[curNode] + curCost) {
                visit[node] = true;
                needVisit.push(curNode);
				// 만약, 이전에 온 노드라면 -1로 초기화 함으로써 간선을 끊어버린다.
                graph[curNode][length] = [-1, node];
            }
        }
    }
}

while (true) {
    const [N, M] = data[curIdx].split(' ').map(Number);
    
    if (N === 0 && M === 0)  break;
    const graph = Array.from(Array(N), () => Array(0));
    const reversedGraph = Array.from(Array(N), () => Array(0));
    let distance = Array(N).fill(Infinity);
    const [S, D] = data[curIdx + 1].split(' ').map(Number);
    curIdx += 2;
   
    for (let i = 0; i < M; i++) {
        const [U, V, P] = data[curIdx + i].split(' ').map(Number);
        graph[U].push([P, V]);
		// reversedGraph는 역추적을 해, 최단 경로의 간선을 잘라내기 위해 사용.
		// 최단 경로에 해당 하는 것을 없애기 위해서 해당 노드의 index를 reversedGraph에 저장한다.
        reversedGraph[V].push([P, U, graph[U].length - 1]);
    }
	// 1번의 디악스트라로, 최단 경로를 찾아낸다.
	dijkstra(S, graph, distance);
	// bfs를 통해 최단 경로를 잘라낸다.
    bfs(D, graph, reversedGraph, distance);
	// 거리 초기화 시키고
    distance = Array(N).fill(Infinity);
	// 그다음의 최단 경로를 구하면 정답
    dijkstra(S, graph, distance);
    if (distance[D] === Infinity) console.log(-1);
    else console.log(distance[D]);
    curIdx += M;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

javascript 5719 거의 최단 경로 33%에서 시간 초과..

yeum0523 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말