[JS][백준]1939_중량제한

문제 번호

1939번: 중량제한

 

 

 

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 이분 탐색
• 너비 우선 탐색
• 분리 집합

 

문제 풀이

 BFS와 이분탐색을 이용하여 문제를 풀었다.

이분탐색을 통하여 한 번의 이동에서 옮길 수 있는 물품들의 중량을 찾는다. 그리고 BFS를 통하여 해당 중량으로 두 공장사이를 무사히 오갈 수 있는지 확인한다.

 

 시간제한 때문에 이분탐색을 사용하여서 중량을 찾아야한다. 이분탐색으로 mid 값을 중량으로 선택한다음, BFS를 통해서 해당 중량이 통과가능한지 확인한다. 만약 해당 중량이 BFS를 통과하지 못한다하면 이분탐색의 범위를 조절하여 mid 값을 조절하여야한다. 

 우리가 찾는것은 물품들의 최대중량이므로 최대값인 right에 해당하는 값이다. 따라서 BFS를 반복적으로 수행하면서 이분탐색의 범위를 조절하다보면 원하는 값을 구 할 수 있다.

 

이분탐색

function binarySearch(n, city, start, end, max) {
  let left = 1;
  let right = max;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (BFS(n, city, start, end, mid)) { // 통과가능한 중량이면 중량을 올린다.
      left = mid + 1;
    }
    else {
      right = mid - 1;
    }
  }
  console.log(right);
}

 

BFS

 BFS는 도착지에 도달하면 더 이상 진행할 필요가 없으므로 return 시켜주었다. 그리고 이분탐색에서 구한 무게를 버틸 수 없는 경우에는 queue에 추가할 필요가 없다.

주어진 문제를 입력받을때 city라는 배열에 각 도시와 도시사이의 다리가 버틸 수 있는 중량을 배열로 push 했다.

city[출발점] = [도착점, 무게제한]의 형식이다. 도시사이에 여러개의 다리가 있는 경우도 있기때문에 같은 도시인 경우 최대 무게를 제외하고 제거해주어야 하나 했었는데 그럴 필요는 없다.

function BFS(n, city, start, end, mid) {
  let visited = new Array(n + 1).fill(false);
  let q = [];
  q.push(start);
  while (q.length !== 0) {
    let cur = q.shift();
    visited[cur] = true;
    if (cur === end) // 도착지 까지 도착.
      return true;

    for (let i = 0; i < city[cur].length; i++) {
      let next = city[cur][i][0]; // 다음 도시.
      let nextCost = city[cur][i][1];
      if (!visited[next] && mid <= nextCost) {
        visited[next] = true;
        q.push(next);
      }
    }
  }
  return false;
}

 

전체코드

function BFS(n, city, start, end, mid) {
  let visited = new Array(n + 1).fill(false);
  let q = [];
  q.push(start);
  while (q.length !== 0) {
    let cur = q.shift();
    visited[cur] = true;
    if (cur === end) // 도착지 까지 도착.
      return true;

    for (let i = 0; i < city[cur].length; i++) {
      let next = city[cur][i][0]; // 다음 도시.
      let nextCost = city[cur][i][1];
      if (!visited[next] && mid <= nextCost) {
        visited[next] = true;
        q.push(next);
      }
    }
  }
  return false;
}

function binarySearch(n, city, start, end, max) {
  let left = 1;
  let right = max;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (BFS(n, city, start, end, mid)) { // 통과가능한 중량이면 중량을 올린다.
      left = mid + 1;
    }
    else {
      right = mid - 1;
    }
  }
  console.log(right);
}

function insert() {
  const input = require('fs').readFileSync('중량제한/input.txt').toString().trim().split('\n');
  const [n, m] = input[0].split(' ').map(Number);

  let city = new Array(n + 1).fill(null).map(_ => []);
  let max = 0;

  for (let i = 1; i <= m; i++) {
    let [from, to, weigth] = input[i].split(' ').map(Number);
    if (weigth > max)
      max = weigth;
    city[from].push([to, weigth]);
    city[to].push([from, weigth]);
  }
  let [start, end] = input[m + 1].split(' ').map(Number);
  binarySearch(n, city, start, end, max); // binarySearch(n, city, start, end, max)
}

insert();

특이사항

  질문게시판을 보니 여러가지 방법의 풀이가 존재했다.