접근법
푸느라 정말 헤맸다.. ◠‿◠ 로직을 정리하고 짜는 습관을 들이자..
여러 풀이를 시도해봤는데 결국 처음 풀이대로 섬마다 번호를 붙여주고 푸는게 답이었다.
그리고 섬의 연결을 탐색할때 습관처럼 DFS로 먼저 풀었는데, 문제를 잘 읽어보자… “가장 짧은” 다리의 길이, 즉 최소거리를 구하는 문제다.
⭐️ 최소 거리 = BFS
DFS로 각 섬마다 번호를 붙여주고, BFS를 통해 최단거리를 찾으면 되는 문제다.
풀이과정
1. 각 섬별로 번호를 붙여준다(1,2,3…)
DFS를 이용!
2. 각 섬마다 다른 섬까지의 최소 거리를 구한다.
최소거리 = BFS를 이용!
2-1. 섬의 테두리 좌표 찾아 queue에 넣기
각 섬의 모든 좌표를 탐색하지 않아도 된다. 섬의 테두리 좌표만 구해 queue에 넣어주고, BFS 탐색을 시작한다. queue에 좌표와 함께 현재 연결 다리 수도 넣어준다.
- ex. [0,0,0] : (0,0) 테두리 좌표, 현재 다리 개수 0
해당 좌표가 섬의 테두리인지 판단하는 기준은, 상하좌우를 살펴봤을때 바다가 있는가? 이다. 하지만, 바다를 발견할때마다 해당 좌표를 queue에 넣어주면, 한 좌표가 queue에 여러번 들어갈 수도 있다.
🤔 queue에 좌표가 중복으로 들어가지 않도록, isBorder라는 bool 변수를 선언해 바다를 발견할시 이를 true로 바꿔주고, 상하좌우 탐색이 모두 끝난 후에 queue에 해당 좌표를 넣어줬다.
2-2. 테두리 좌표 queue를 기반으로, BFS 탐색
queue에서 테두리 원소를 빼내 상하좌우를 확인해본다.
- 이때, 바다이면 큐에 [해당원소x, 해당원소y, 현재 연결된 다리수 + 1]을 넣어준다.
- 만약 바다가 아닌 현재 섬과 다른 번호라면, 다른 섬에 도달했다는 뜻이다. 현재 연결된 다리수로 최솟값을 갱신해준다.
🤔 코드를 다 작성한 후에 시간을 줄일 수 있는 방법이 없을까? 고민했다.
생각해보니 bfs로 1번섬에서 나머지 섬까지의 연결을 확인하고나면, 2번섬은 1번섬과의 연결을 확인하지 않아도 되는데, 내가 짠 로직에서는 자기 자신을 제외한 모든 섬과의 연결을 매번 확인했다. 또한, N개의 섬이 존재할 때, N번 섬은 나머지 섬에서 모든 연결이 확인되었기에 더이상 탐색할 필요가 없다.
- N개의 섬이 존재할때 1번섬에서 N-1번, 2번섬에서 N-1번 .. 이기 때문에 N(N-1) = 대략 N^2 번 bfs 함수가 실행됨.
그래서 이미 연결을 확인한 섬을 중복체크 하지 않기 위해, check 배열을 만들어 탐색이 끝나면 해당 섬의 인덱스로 참조되는 값을 true로 바꿔주고, bfs에서 연결을 상하좌우를 확인할때도 (현재섬과 다른번호 && 연결을 확인하지 않은 섬) 일때만 최솟값을 갱신하도록 했다.
또한 마지막 섬은 앞에서 다 연결을 확인했기 때문에, 탐색하지 않아도 되므로 마지막 섬을 탐색하는 경우는 for문에서 제외해줬다.
- 1번 섬에서 N-1, 2번 섬에서 N-2, 3번 섬에서 N-3, …. N-1 번 섬에서 1 .. 씩 탐색. 위의 경우보다는 시간이 훨씬 단축 될 것!
코드
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n");
const N = Number(input.shift());
const map = input.map((v) => v.split(" ").map(Number));
const dir = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1],
];
let visited = Array.from(Array(N), () => Array(N).fill(false));
let min = Number.MAX_VALUE;
function CountIsland(i, j, num) {
visited[i][j] = true;
map[i][j] = num;
for (let d of dir) {
const [dx, dy] = [i + d[0], j + d[1]];
if (isValidRange(dx, dy) && !visited[dx][dy] && map[dx][dy] === 1) {
CountIsland(dx, dy, num);
}
}
}
function isValidRange(i, j) {
return i >= 0 && j >= 0 && i < N && j < N ? true : false;
}
function connectIsland(islandNumber, check) {
const queue = [];
visited = Array.from(Array(N), () => Array(N).fill(false));
let isBorder = false;
// 해당 섬 테두리 찾기
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (!visited[i][j] && map[i][j] === islandNumber) {
visited[i][j] = true;
for (let d of dir) {
const [dx, dy] = [i + d[0], j + d[1]];
if (isValidRange(dx, dy) && !visited[dx][dy] && map[dx][dy] === 0) {
isBorder = true;
}
}
if (isBorder) {
queue.push([i, j, 0]);
isBorder = false;
}
}
}
}
while (queue.length) {
let [cx, cy, count] = queue.shift();
for (let d of dir) {
const [dx, dy] = [cx + d[0], cy + d[1]];
if (isValidRange(dx, dy) && !visited[dx][dy]) {
if (map[dx][dy] === 0) {
visited[dx][dy] = true;
queue.push([dx, dy, count + 1]);
} else if (map[dx][dy] !== islandNumber && !check[islandNumber - 1]) {
min = Math.min(min, count);
}
}
}
}
}
function solve() {
// 섬별 번호 붙이기
let islandNumber = 1;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (!visited[i][j] && map[i][j] === 1) {
CountIsland(i, j, islandNumber);
islandNumber++;
}
}
}
// 섬마다 BFS 연결해보기
let check = new Array(islandNumber).fill(false);
for (let i = 1; i < islandNumber; i++) {
connectIsland(i, check);
check[i - 1] = true;
}
console.log(min);
}
solve();