백준 2146 다리 만들기

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const check = (x, y, n) => {
  return x >= 0 && y >= 0 && x < n && y < n;
};
const solution = (input) => {
  const n = +input.shift();
  const table = input.map((e) => e.split(" ").map(Number));
  let visited = Array.from(Array(n), () => Array(n).fill(0));

  let islandNum = 0;

  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  const dfs = (x, y, islandNum) => {
    visited[x][y] = 1;
    table[x][y] = islandNum;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (check(nx, ny, n) && !visited[nx][ny] && table[nx][ny]) {
        dfs(nx, ny, islandNum);
      }
    }
  };
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (table[i][j] && !visited[i][j]) {
        dfs(i, j, ++islandNum);
      }
    }
  }

  const bfs = (islandNum) => {
    const queue = [];
    let visited2 = Array.from(Array(n), () => Array(n).fill(0));

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (table[i][j] === islandNum) {
          queue.push([i, j]);
        }
      }
    }
    let cnt = 0;
    while (queue.length) {
      let qlen = queue.length;
      while (qlen--) {
        // 한 루프에 들어간 애들만 쫙 빼줌.
        // 즉 다시 여기로 돌아왔을 때 queue 내용물이 완전히 바뀌어있다는 뜻.
        let [x, y] = queue.shift();
        for (let i = 0; i < 4; i++) {
          const nx = x + dx[i];
          const ny = y + dy[i];
          if (!check(nx, ny, n)) continue;
          if (table[nx][ny] !== 0 && table[nx][ny] !== islandNum) {
            // 다음 방문할 곳이 육지이고 섬의 번호가 바뀌었다면. => 다음 섬에 도착한 것.
            return cnt;
          }
          if (table[nx][ny] === 0 && !visited2[nx][ny]) {
            // 다음 방문할 곳이 바다이면
            visited2[nx][ny] = 1;
            queue.push([nx, ny]);
          }
        }
      }
      cnt++;
    }
  };
  let answer = Number.MAX_SAFE_INTEGER;
  for (let i = 1; i <= islandNum; i++) {
    // 처음 기준으로 섬의 번호가 1인 곳은 죄다 탐색.
    answer = Math.min(answer, bfs(i));
  }
  return answer;
};

console.log(solution(input));

• dfs를 이용해 섬에 번호를 부여한다.
• 1번째로 방문한 육지와 그와 연결된 땅은 전부 1, 2번째로 방문한 육지와 그와 연결된 땅은 전부 2가 되는 것.
• bfs를 이용해 다음 섬까지의 거리를 측정(코드의 주석 참고)

복습

bfs를 더 직관적이게 이해가 되도록 바꿨다.

const sol = (n, graph) => {
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  let visited = Array.from(Array(n), () => Array(n).fill(0));

  let islandNum = 0;

  // 섬 번호를 입력하고 돌아옴
  const dfs = (x, y, islandNum) => {
    visited[x][y] = 1;
    graph[x][y] = islandNum;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      if (!visited[nx][ny] && graph[nx][ny]) {
        dfs(nx, ny, islandNum);
      }
    }
  };

  // dfs 호출
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (!visited[i][j] && graph[i][j]) {
        dfs(i, j, ++islandNum);
      }
    }
  }

  // 해당 섬에서 다른 섬까지 거리 최소값을 구해온다.
  const bfs = (islandNum) => {
    const queue = [];
    visited = Array.from(Array(n), () => Array(n).fill(0));

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (graph[i][j] === islandNum) {
          queue.push([i, j]);
        }
      }
    }

    let cnt = 0;

    while (queue.length) {
      let cur = queue.length;

      for (let cycle = 0; cycle < cur; cycle++) {
        const [x, y] = queue.shift();

        for (let i = 0; i < 4; i++) {
          const nx = x + dx[i];
          const ny = y + dy[i];
          if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
          if (graph[nx][ny] !== 0 && graph[nx][ny] !== islandNum) {
            return cnt;
          }

          if (graph[nx][ny] === 0 && !visited[nx][ny]) {
            visited[nx][ny] = 1;
            queue.push([nx, ny]);
          }
        }
      }
      cnt++;
    }
  };
  let answer = Number.MAX_SAFE_INTEGER;
  // answer, bfs를 비교해 값 갱신
  for (let i = 1; i <= islandNum; i++) {
    answer = Math.min(answer, bfs(i));
  }

  return answer;
};