백준1948 - 임계경로 (위상정렬 & 백트래킹) node.js

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

문제는 시작 도시에서 도착 도시까지의 최대로 걸리는 시간과, 최대 시간에 맞춰 도착하는 도시의 갯수를 출력하는 문제다.

 

문제 해결 방식

모든 도로가 일방 통행(양방향 그래프)이며, 싸이클이 없다(위상 정렬 가능)는 점에서 최근에 학습한 위상정렬로 풀이하는 것으로 접근했다. (다익스트라로도 풀이가 가능할 것 같지만, node.js 환경이다 보니, 최소힙 구현까지는 번거로워 위상 정렬을 선택한 이유도 있다.)

그리고 이때 DP 프로그래밍을 활용하여, 시작지점에서 다른 지점으로 이동할 때 걸리는 최대시간을 저장하는 방식으로 데이터를 저장했다.

위상 정렬 부분 소스 코드

  const [[N], _, ...arr] = data.map((el) => el.split(" ").map(Number));
  const [start, end] = arr.pop();

  const graph = Array.from({ length: N + 1 }, () => []);
  // const graph_reverse = Array.from({ length: N + 1 }, () => []); 역추적관련 부분
  const rank = Array.from({ length: N + 1 }, () => 0);

  arr.forEach(([s, e, w]) => {
    graph[s].push([e, w]); // 도착지점과 가중치를 원소로 하는 배열을 그래프에 추가
    // graph_reverse[e].push([s, w]);
    rank[e]++; // 진입 차수 증가
  });

  const dp = Array.from({ length: N + 1 }, () => 0);

  const queueForSort = [start];
  let queueIdx1 = 0;

  while (queueIdx1 < queueForSort.length) {
    const node = queueForSort[queueIdx1++];

    graph[node].forEach(([next, w]) => {
      rank[next]--;
      dp[next] = Math.max(dp[next], dp[node] + w); // 최대 시간 메모라이징
      if (!rank[next]) queueForSort.push(next);
    });
  }

  const result1 = dp[end];

위 소스 코드가 이해가 안된다면, 이전에 포스팅한 아래 링크를 참고하길 바란다!

위상정렬에 대해 설명한 포스팅

2024.01.23 - [개발/algorithm] - 백준2252 - 줄 세우기 (위상정렬) node.js

 

이후 도착지점에서부터 백트래킹하여, 최대 시간에 딱 맞춰 도착할 수 있는 도시의 갯수를 구한다.

해당 로직을 위한 논리는 다음 예시를 따른다.

위와 같이 정점 A,B,C,D가 있고, 정점 사이에 가중치가 있다고 한다면 도착지점인 D에 도착하는 최대 시간은 4이다. (A=>B=>D 경로로 이동)

도착 지점에서 각 간선의 가중치를 뺀 경우와, 해당 도착지점까지의 거리가 같다면 최대거리를 만족한다고 볼 수 있다.

즉, A에서 D까지의 최대거리(4) - B에서 D까지의 거리(2) == A에서 B까지의 거리(2) 이므로, B는 최대 시간에 맞춰 도착하는 도시.

A에서 D까지의 최대거리(4) - C에서 D까지의 거리(1) != A에서 C까지의 거리(1) 이므로, C는 최대 시간에 맞춰 도착하는 도시가 아니다.

 

그리고 위 로직을 코드로 옮겨적으면 다음과 같다.

백트래킹 소스 코드

  // 방문 여부 체크
  const visited = Array.from({ length: N + 1 }, () => false);
  // 최대 시간에 맞춰 도착하는 도시의 갯수를 담는 변수
  let result2 = 0;

  const queueForBacktrack = [end]; // 도착지점에서 시작
  let queueIdx2 = 0;

  while (queueIdx2 < queueForBacktrack.length) {
    const node = queueForBacktrack[queueIdx2++];

    graph_reverse[node].forEach(([next, w]) => {
      // 해당 도시 도착 시간 - 가중치, 다음 도시 도착 시간 비교
      if (dp[node] - w === dp[next]) {
        // 일치 시 이는 최대 시간에 맞춰 도착하는 도시의 갯수
        result2++;

        if (!visited[next]) {
          queueForBacktrack.push(next);
          visited[next] = true;
        }
      }
    });
  }
  console.log(result2);

 

전체 소스 코드

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

function solution(data) {
  const [[N], _, ...arr] = data.map((el) => el.split(" ").map(Number));
  const [start, end] = arr.pop();

  const graph = Array.from({ length: N + 1 }, () => []);
  const graph_reverse = Array.from({ length: N + 1 }, () => []);
  const rank = Array.from({ length: N + 1 }, () => 0);

  arr.forEach(([s, e, w]) => {
    graph[s].push([e, w]);
    graph_reverse[e].push([s, w]);
    rank[e]++;
  });

  const dp = Array.from({ length: N + 1 }, () => 0);

  const queueForSort = [start];
  let queueIdx1 = 0;

  while (queueIdx1 < queueForSort.length) {
    const node = queueForSort[queueIdx1++];

    graph[node].forEach(([next, w]) => {
      rank[next]--;
      dp[next] = Math.max(dp[next], dp[node] + w);
      if (!rank[next]) queueForSort.push(next);
    });
  }

  const result1 = dp[end];
  console.log(result1);

  const visited = Array.from({ length: N + 1 }, () => false);
  let result2 = 0;

  const queueForBacktrack = [end];
  let queueIdx2 = 0;

  while (queueIdx2 < queueForBacktrack.length) {
    const node = queueForBacktrack[queueIdx2++];

    graph_reverse[node].forEach(([next, w]) => {
      if (dp[node] - w === dp[next]) {
        result2++;

        if (!visited[next]) {
          queueForBacktrack.push(next);
          visited[next] = true;
        }
      }
    });
  }
  console.log(result2);
}

solution(input);