백준 1738 골목길 js

1738번: 골목길

이번에 풀어 볼 문제는 벨만포드 문제입니다.

 

문제 속에 핵심찾기.

문제를 읽어보면 어떤 경로를 갔을 때 금품을 갈취당하거나, 획득하게 됩니다.

따라서 비용이 음수인 간선과 양수인 간선이 존재하며, 금품의 양은 음수가 될 수 있다는것으로 보아 벨만포드 알고리즘을 적용하기에 적합하다는 것을 알 수 있습니다.

 

정답은 민승이네 집(1번 노드)에서 코레스코 콘도(N번 노드)로 금품의 양이 최대가 되는 경로를 출력하면 됩니다.

∴  주의 할 점.

경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다. 어떠한 경우에 그런 상황이 발생하는지 생각해 보자. 그러한 경우에는 -1을 출력하도록 한다.

코레스코 콘도(N번 노드)까지 가는 길에 금품의 양이 무한대가 되는 싸이클이 존재한다면 -1을 출력해주어야 합니다.

 

풀이.

벨만포드 알고리즘은 특정 노드로부터 다른 노드까지 최적의 비용을 구할 수 있으며, 음의 간선이 포함된 경우에도 사용할 수 있습니다. 또한 음수 간선의 순환을 감지할 수 있습니다.

 

하지만 모든 영역에 대해 싸이클 여부를 체크하기 때문에 단순히 싸이클이 존재한다고 -1을 출력해서는 안됩니다.

민승이네 집(1번 노드)에서 코레스코 콘도(N번 노드)로 가는 경로에 싸이클이 존재할 경우에만 -1을 출력해 주어야하는게 핵심입니다.

 

비용에 -1을 곱한 값을 삽입하여 금품의 양이 최소가 되는 경로를 구해주겠습니다.

 

1. bfs로 N번 노드부터 1번 노드까지 역추적하여 방문 노드를 체크해주겠습니다.

2. 벨만포드 알고리즘을 통해 path배열을 만들어 도착노드에 출발노드를 기록해줍니다.

  2 - 1. N번째 반복할 때 경로가 방문 노드일 경우 비용이 갱신된다면 음수의 싸이클이 존재하므로 -1을출력합니다.

3. 2 - 1번의 경우가 해당되지 않는다면 path배열에 기록했던 경로를 1번부터 순서대로 출력해줍니다.

 

구현.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
// 모든 길이 이어져있지 않을 수 있다.
// N에서 출발해서 갈 수 있는 노드의 경우에 무한 싸이클이 존재할 때에만 -1출력
let N, M;
let edges = [];
let dist = [];
let path = [];
let result = []; 
let visit = []; // 출발노드에서 도착노드까지 방문한 노드를 기록하기 위한 배열
let graph = []; // 도착노드에서부터 역추적을 위한 graph배열

function bfs(start) {
  let queue = [start];
  visit[start] = true;
  let index = 0;

  while (queue.length > index) {
    const n = queue[index++];

    graph[n].forEach((nextNode) => {
      if (!visit[nextNode]) {
        visit[nextNode] = true;
        queue.push(nextNode);
      }
    });
  }
}

function bf() {
  for (let i = 1; i <= N; i++) {
    for (let j = 0; j < M; j++) {
      const [start, end, cost] = edges[j];
      if (dist[end] > dist[start] + cost) {
        dist[end] = dist[start] + cost;
        path[end] = start;
        // 방문 노드에 싸이클이 생긴다면 true를 리턴
        if (i === N && visit[end]) return true;
      }
    }
  }
  return false;
}

rl.on("line", function (line) {
  if (!N) {
    [N, M] = line.split(" ").map((n) => +n);
    dist = Array.from({ length: N + 1 }, () => Infinity);
    visit = Array.from({ length: N + 1 }, () => false);
    graph = Array.from({ length: N + 1 }, () => []);
  } else {
    const [u, v, w] = line.split(" ").map((n) => +n);
    edges.push([u, v, -w]); // 음의 싸이클 존재를 구하기 위해 비용을 -1 곱한 값으로 넣어줍니다.
    graph[v].push(u); // 역추적하기 위해 도착과 출발을 반대로 넣어줍니다.
    if (edges.length === M) {
      dist[1] = 0;
      bfs(N); // 도착노드로 부터 출발노드까지 기록을 위해 N(도착노드)으로 시작해줍니다.
      const isInf = bf();
      if (isInf) console.log(-1);
      else {
        // path배열을 통해 N부터 1까지 순서대로 삽입.
        let start = N;
        while (true) {
          result.push(start);
          if (start === 1) break;
          start = path[start];
        }
  		
        // 1번부터 N번까지 출력
        console.log(result.reverse().join(" "));
      }
      rl.close();
    }
  }
});