[백준] 1753번 최단경로 - 자바스크립트

문제

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

코드

const MinHeap = (function () {
  function MinHeap() {
    this.heap = [-Infinity];
  }

  MinHeap.prototype.size = function () {
    return this.heap.length - 1;
  };

  MinHeap.prototype.push = function (val) {
    this.heap.push(val);
    this._upheap(this.size());
  };

  MinHeap.prototype._upheap = function (pos) {
    let pushed = this.heap[pos];
    let parentPos = Math.floor(pos / 2);

    while (pushed.dist < this.heap[parentPos].dist) {
      this.heap[pos] = this.heap[parentPos];
      pos = parentPos;
      parentPos = Math.floor(pos / 2);
    }

    this.heap[pos] = pushed;
  };

  MinHeap.prototype.pop = function () {
    if (this.size() === 1) return this.heap.pop();

    let popped = this.heap[1];
    this.heap[1] = this.heap.pop();
    this._downheap(1, this.size());
    return popped;
  };

  MinHeap.prototype._downheap = function (pos, lastPos) {
    const target = Math.floor(lastPos / 2);
    let lastVal = this.heap[pos];
    let childPos;

    while (pos <= target) {
      childPos = pos * 2;
      if (childPos < lastPos && this.heap[childPos].dist > this.heap[childPos + 1].dist) childPos += 1;
      if (lastVal.dist <= this.heap[childPos].dist) break;
      this.heap[pos] = this.heap[childPos];
      pos = childPos;
    }
    this.heap[pos] = lastVal;
  };

  return MinHeap;
})();

function sol(input) {
  const [V, E] = input[0].split(' ').map(Number);
  const k = +input[1];

  const graphs = Array.from({ length: V + 1 }, () => new Array());

  for (let i = 2, iter = input.length; i < iter; i++) {
    const [from, to, w] = input[i].split(' ').map(Number);
    graphs[from].push({ node: to, dist: w });
  }

  const visits = new Array(V + 1).fill(0);
  const distance = new Array(V + 1).fill(Infinity);
  distance[k] = 0;

  const pq = new MinHeap();
  pq.push({ node: k, dist: 0 });

  while (pq.size()) {
    const { node, dist } = pq.pop();

    if (visits[node]) continue;
    visits[node] = 1;

    const nexts = graphs[node];
    if (!nexts.length) continue;

    for (let i = 0, iter = nexts.length; i < iter; i++) {
      const { node: nextNode, dist: nextDist } = nexts[i];

      if (distance[nextNode] > dist + nextDist) {
        distance[nextNode] = dist + nextDist;
        pq.push({ node: nextNode, dist: distance[nextNode] });
      }
    }
  }

  return distance
    .slice(1)
    .map((e) => (e === Infinity ? 'INF' : e))
    .join('\n');
}

const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

풀이

조건

정점 V, 간선 E 개수가 주어진다. (범위는 1 <= V <= 2만, 1 <= E <= 30만)

- 모든 정점은 1~V까지의 번호가 매겨진다.

- 간선 E는 연결+거리값을 가지고 있다.

K는 출발할 정점의 번호다.

방향그래프 정보는 "u v w"의 순서대로 주어진다.

- 정점 u에서 정점 v까지 거리가 w임을 의미한다.

- u와 v는 서로 다르며, w는 10 이하의 자연수이다.

- 서로 다른 두 정점 사이에, 여러 간선이 존재할 수 있다.(예를 들면, "1 2 3", "1 2 4" 가 주어질 수 있다.)

K부터 시작해서 1~V번까지 각각 가장 빠른 최소거리를 출력한다.

풀이방향을 생각해보면..

한 정점을 기준으로, 다른 정점으로 가는 최단거리를 구해야 하는 문제다.

다익스트라 최단경로 알고리즘을 이용하면 될 듯 하다.

다익스트라에서는 3가지 배열이 필요하다.

1. 각 정점과 바로 연결된 노드의 정보를 담은 2차원 리스트. = 변수명 graphs

2. K 정점에서 1~V번까지의 최단거리를 담은 1차원 리스트. = 변수명 distance

3. 각 정점의 방문여부를 조회할 1차원 리스트. = 변수명 visits

그럼 다익스트라대로 대충 시나리오를 짜보면,

1. distance 배열에서 K 정점 -> K 정점으로의 거리를 0으로 갱신한다.

2. distance 최소거리인 current 정점(처음에는 K정점)과 연결된 graphs[current] 정점들을 탐색한다.

current 정점의 visits 배열을 1(방문했음)으로 표시한다.

3. 다음 next 정점까지가 최소거리(distance[current] +연결거리 < distance[next]) 라면 distance[next] 값을 갱신한다.

4. 2~3번의 과정을 반복한다.

가장 병목이 될 구간은, 2번이다.

distance 배열의 크기가 V(2만)이다.

여기서 방문하지않은 + 최소거리를 찾을 때 마다 O(N)이 소요된다.

그럼 최소거리를 바로 가져올 수 있도록 Priority Queue(최소힙)를 만들어 쓰면 되겠다.

마지막으로

visits 배열 원소가 모두 1이면 distance 배열이 모두 갱신되었을 것이고,

distance 배열에서 Infinity값만 "INF"로 바꿔준 뒤 출력하면 된다.

주석 포함 코드

// PQ(inputValue.dist 기준으로 정렬되는 최소힙).
const MinHeap = (function () {
  function MinHeap() {
    this.heap = [-Infinity];
  }

  MinHeap.prototype.size = function () {
    return this.heap.length - 1;
  };

  MinHeap.prototype.push = function (val) {
    this.heap.push(val);
    this._upheap(this.size());
  };

  MinHeap.prototype._upheap = function (pos) {
    let pushed = this.heap[pos];
    let parentPos = Math.floor(pos / 2);

    while (pushed.dist < this.heap[parentPos].dist) {
      this.heap[pos] = this.heap[parentPos];
      pos = parentPos;
      parentPos = Math.floor(pos / 2);
    }

    this.heap[pos] = pushed;
  };

  MinHeap.prototype.pop = function () {
    if (this.size() === 1) return this.heap.pop();

    let popped = this.heap[1];
    this.heap[1] = this.heap.pop();
    this._downheap(1, this.size());
    return popped;
  };

  MinHeap.prototype._downheap = function (pos, lastPos) {
    const target = Math.floor(lastPos / 2);
    let lastVal = this.heap[pos];
    let childPos;

    while (pos <= target) {
      childPos = pos * 2;
      if (childPos < lastPos && this.heap[childPos].dist > this.heap[childPos + 1].dist) childPos += 1;
      if (lastVal.dist <= this.heap[childPos].dist) break;
      this.heap[pos] = this.heap[childPos];
      pos = childPos;
    }
    this.heap[pos] = lastVal;
  };

  return MinHeap;
})();

function sol(input) {
  const [V, E] = input[0].split(' ').map(Number);
  const k = +input[1];
	
    // Edge의 정보들을 담은 2차원리스트
  const graphs = Array.from({ length: V + 1 }, () => new Array());

  for (let i = 2, iter = input.length; i < iter; i++) {
  	// from->to까지 w의 정보를 graphs에 넣어준다.
    const [from, to, w] = input[i].split(' ').map(Number);
    graphs[from].push({ node: to, dist: w });
  }

	// 방문 정보가 담긴 visits, 거리 정보가 담긴 distance
  const visits = new Array(V + 1).fill(0);
  const distance = new Array(V + 1).fill(Infinity);
  distance[k] = 0;

	// pq에서 현재탐색노드(K)부터 탐색을 시작할 예정. K->K는 거리 0
  const pq = new MinHeap();
  pq.push({ node: k, dist: 0 });

  while (pq.size()) {
  	// pq에 더이상 노드가 없을때까지 탐색.
    const { node, dist } = pq.pop();

	// 방문(최소값 갱신)한 노드는 패스.
    if (visits[node]) continue;
    visits[node] = 1;

	// 방문했는데, 이 노드에서 갈 수 있는 다른 노드가 없다면 패스.
    const nexts = graphs[node];
    if (!nexts.length) continue;

    for (let i = 0, iter = nexts.length; i < iter; i++) {
      const { node: nextNode, dist: nextDist } = nexts[i];
		// 다음노드의 최소거리 > 현재노드최소거리+연결된거리 이면, 최소값 갱신 가능.
      if (distance[nextNode] > dist + nextDist) {
        distance[nextNode] = dist + nextDist;
        // 최소값이 갱신되었다면 정보를 pq에 넣어준다.
        // 왜?. 기존 pq에 3번노드가 4인 정보가 있다면, 갱신에 의해 3번노드거리가 2가 될수도.
        // 어차피 3번:2가 먼저 pq로부터 나올거고, 다음 3번:4는 visits 배열에 의해 필터링된다.
        pq.push({ node: nextNode, dist: distance[nextNode] });
      }
    }
  }

	// INF 필터링 후 출력코드.
  return distance
    .slice(1)
    .map((e) => (e === Infinity ? 'INF' : e))
    .join('\n');
}


// 입력받기
const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

마지막으로 코드가 난잡해서 조금 예쁘게? 함수단위로 묶어보았다.

// PQ
const MinHeap = (function () {
  function MinHeap() {
    this.heap = [-Infinity];
  }

  MinHeap.prototype.size = function () {
    return this.heap.length - 1;
  };

  MinHeap.prototype.push = function (val) {
    this.heap.push(val);
    this._upheap(this.size());
  };

  MinHeap.prototype._upheap = function (pos) {
    let pushed = this.heap[pos];
    let parentPos = Math.floor(pos / 2);

    while (pushed.dist < this.heap[parentPos].dist) {
      this.heap[pos] = this.heap[parentPos];
      pos = parentPos;
      parentPos = Math.floor(pos / 2);
    }

    this.heap[pos] = pushed;
  };

  MinHeap.prototype.pop = function () {
    if (this.size() === 1) return this.heap.pop();

    let popped = this.heap[1];
    this.heap[1] = this.heap.pop();
    this._downheap(1, this.size());
    return popped;
  };

  MinHeap.prototype._downheap = function (pos, lastPos) {
    const target = Math.floor(lastPos / 2);
    let lastVal = this.heap[pos];
    let childPos;

    while (pos <= target) {
      childPos = pos * 2;
      if (childPos < lastPos && this.heap[childPos].dist > this.heap[childPos + 1].dist) childPos += 1;
      if (lastVal.dist <= this.heap[childPos].dist) break;
      this.heap[pos] = this.heap[childPos];
      pos = childPos;
    }
    this.heap[pos] = lastVal;
  };

  return MinHeap;
})();

// 다익스트라
function dijkstra(V, k, graphs) {
  const distance = new Array(V + 1).fill(Infinity);
  const visits = new Array(V + 1).fill(0);
  distance[k] = 0;

  const pq = new MinHeap();
  pq.push({ node: k, dist: 0 });

  while (pq.size()) {
    const { node, dist } = pq.pop();

    if (visits[node]) continue;
    visits[node] = 1;

    const nextNodes = graphs[node];
    if (!nextNodes.length) continue;

    for (let { node: nextNode, dist: nextDist } of nextNodes) {
      if (distance[nextNode] > dist + nextDist) {
        distance[nextNode] = dist + nextDist;
        pq.push({ node: nextNode, dist: distance[nextNode] });
      }
    }
  }

  return distance;
}

// 닿을수 없는 노드 필터링 함수
function filterDist(dist) {
  return dist === Infinity ? 'INF' : dist;
}


// 본격 실행해야 할 함수
function sol(input) {
  const [V, E] = input[0].split(' ').map(Number);
  const k = +input[1];

  const graphs = Array.from({ length: V + 1 }, () => new Array());

  for (let inputStr of input.slice(2)) {
    const [from, to, w] = inputStr.split(' ').map(Number);
    graphs[from].push({ node: to, dist: w });
  }

  const distance = dijkstra(V, k, graphs);

  return distance.slice(1).map(filterDist).join('\n');
}

// 백준 입력받는 부분
const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

저작자표시

'DS & Algorithm > baekjoon' 카테고리의 다른 글

[백준] 25632번 소수부르기게임 - 자바스크립트 (0)	2022.09.27
[백준] 17406번 배열 돌리기 4 - 자바스크립트 (0)	2022.04.15
[백준] 13460번 구슬 탈출 2 - 자바스크립트 (0)	2022.03.25
[백준] 1541번 잃어버린 괄호 - JavaScript(NodeJS) (0)	2021.07.19
[백준] 2108번 통계학 - JavaScript(NodeJS) (0)	2021.07.18

문제

코드

풀이

주석 포함 코드

마지막으로 코드가 난잡해서 조금 예쁘게? 함수단위로 묶어보았다.

'DS & Algorithm > baekjoon' 카테고리의 다른 글

티스토리툴바