백준 17472 다리 만들기2

17472번: 다리 만들기 2

문제 핵심 파악하기.

1. 모든 섬을 최소 길이의 다리로 모두 이어줄 때 다리 길이의 합을 출력하는 문제입니다.

2. 섬과 섬을 다리로 이어줄 때 길이는 2이상이어야 하며,  다리가 교차하더라도 교차 구간의 길이가 1이 되는 것이 아닌 각각의 다리의 길이를 포함하여야 합니다.

 

풀이.

1. 각각의 섬을 다음과 번호를 붙여 구분해 줄 것입니다.

섬 넘버링 해주기.

2. 각각의 섬이 다른 섬으로 이동할 때 최소 거리를 완전 탐색 + bfs를 이용하여 구해줍니다.

 

3. 이제 간단한 vertex와 edge를 가지는 그래프 형식으로 생각해 주겠습니다.

 1번 섬에서 2번 섬으로 갈 때 최소비용 2 간단히 하여[ 1 -> 2 [2], 2 -> 3 [2], 3 -> 5 [2], 3 -> 4 [3] ]

(1번 노드에서 2번 노드로 가중치 2 비용)이라 생각하고 edges를 하나의 배열에 모아줍니다.

 

4. union-find 알고리즘을 통해 모든 노드가 이어질 때 최소 비용을 구해줍니다.

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let N, M;
let map = [];
let distance = [];
const INF = Infinity;
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

// 최소 스패닝 비용을 구하기 위해 union-find를 만들어 주었습니다.
function UnionFind(N) {
  this.parents = Array.from({ length: N + 1 }, (_, i) => i);

  this.getParent = (num) => {
    if (this.parents[num] === num) return num;
    return (this.parents[num] = this.getParent(this.parents[num]));
  };

  this.unionParents = (a, b) => {
    const aParent = this.getParent(a);
    const bParent = this.getParent(b);

    if (aParent > bParent) this.parents[aParent] = bParent;
    else this.parents[bParent] = aParent;
  };

  this.findParent = (a, b) => {
    const aParent = this.getParent(a);
    const bParent = this.getParent(b);

    return aParent === bParent;
  };
}

// 각각의 섬을 구분하기 위해 넘버링하는 함수 입니다.
function isLandNumbering(i, j, isLandNum) {
  const queue = [[i, j]];

  let index = 0;
  while (queue.length > index) {
    const [y, x] = queue[index++];
    map[y][x] = isLandNum;

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
      if (map[ny][nx] === -1) {
        queue.push([ny, nx]);
      }
    }
  }
}

// 섬에서 다른 섬으로 이동할 때 최소 비용을 구하는 함수입니다.
function searchMinDist(queue, now) {
  let index = 0;
  while (queue.length > index) {
    const [y, x, dist, dir] = queue[index++];

    const stack = [];
    if (dir === -1) {
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];

        stack.push([ny, nx, i]);
      }
    } else {
      const nx = x + dx[dir];
      const ny = y + dy[dir];

      stack.push([ny, nx, dir]);
    }

    while (stack.length) {
      const [ny, nx, nDir] = stack.pop();

      if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
      const next = map[ny][nx];
      if (next === now) continue;
      if (next !== 0 && dist > 1) {
        distance[now][next] = Math.min(distance[now][next], dist);
      }
      if (next === 0) {
        queue.push([ny, nx, dist + 1, nDir]);
      }
    }
  }
}

rl.on("line", function (line) {
  if (!N) {
    [N, M] = line.split(" ").map(Number);
    visit = Array.from({ length: N }, () => Array(M).fill(false));
  } else {
    map.push(line.split(" ").map((n) => (n === "1" ? -1 : +n)));

    if (map.length === N) {
      rl.close();
    }
  }
}).on("close", function () {
  // 섬 구역별로 번호 매기기
  let isLandNumber = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (map[i][j] === -1) {
        isLandNumber += 1;
        isLandNumbering(i, j, isLandNumber);
      }
    }
  }

  distance = Array.from({ length: isLandNumber + 1 }, () =>
    Array(isLandNumber + 1).fill(INF)
  );

  // 섬에서 섬으로 갈 수 있는 최소 거리 구하기
  // 완전 탐색하여 각 섬에서 각 섬으로 탐색해야 합니다.
  for (let k = 1; k <= isLandNumber; k++) {
    const queue = [];
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (map[i][j] === k) {
          queue.push([i, j, 0, -1]);
        }
      }
    }

    searchMinDist(queue, k);
  }

  const edges = [];
  for (let i = 1; i <= isLandNumber; i++) {
    for (let j = 1; j <= isLandNumber; j++) {
      const dist = distance[i][j];
      if (dist !== INF) {
        edges.push([i, j, dist]);
      }
    }
  }

  const uf = new UnionFind(isLandNumber);
  let result = 0;
  edges.sort((a, b) => a[2] - b[2]);
  for (let i = 0; i < edges.length; i++) {
    const [from, to, dist] = edges[i];
    if (!uf.findParent(from, to)) {
      uf.unionParents(from, to);
      result += dist;
    }
  }

  // 갈 수 없는 섬이 있는지 확인
  let flag = false;
  for (let i = 2; i <= isLandNumber; i++) {
    if (!uf.findParent(1, i)) {
      flag = true;
      break;
    }
  }
  
  // flag === true(갈 수 없는 섬이 있다)라면 -1을 출력
  // 아니면 최소 비용 출력
  console.log(flag ? -1 : result);

  process.exit();
});