준겸이는 칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다.
준겸이는 본인의 집이 있는 위치를 기준으로 삼아 이라고 표시하기로 했다. 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸 걸어가면, 위치 에 도달할 것이다. 마찬가지로 아래로 한 칸 걸어가면, 위치 에 도달할 것이다. 준겸이가 에서 칸 오른쪽으로 걸어가면, 한 바퀴를 돌아 다시 원래 자리로 되돌아오게 된다. 비슷하게 에서 칸 아래로 걸어가면, 으로 돌아오게 된다. 행성은 연결되어 있기 때문에, 준겸이가 에서 왼쪽으로 한 칸 걸어가면 위치 에 도달할 것이다. 마찬가지로 준겸이가 에서 위로 한 칸 걸어가면 에 도달하게 된다.
준겸이는 행성을 탐험하려고 한다. 만약 준겸이가 비어 있는 어떤 칸 에서 시작해, 숲에 막히지 않고 비어 있는 칸 에 도달할 수 있다면 와 는 같은 구역이다. 반대로, 도달할 수 없다면 와 는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.
첫 번째 줄에 과 이 공백을 사이에 두고 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 개의 칸에 대한 정보가 주어진다. 두 번째 줄에서부터 번째 줄에 주어지는 번째 정수는 칸 에 대한 정보이다. 만약 0이라면 비어 있는 것이고, 1이라면 숲으로 막혀 있는 것이다.
탐험할 수 있는 구역의 개수를 출력한다.
7 8
0 0 1 1 0 0 0 0
0 1 1 1 1 0 1 0
1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 0
1 1 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 1 1 1 1 0 0
2
또한 원티드 쇼미더코드 2022 3회차
에 지원해서 풀었던 문제이다. 그 땐 알고리즘 유형을 익히지 못했기에 이게 DFS/BFS 문제인지도 모르고 지레 겁먹은채로 끙끙거렸던 기억이 난다. (도넛 행성 이미지도 한 몫 했다고 생각한다.)
여타 다른 DFS/BFS와 똑같은 문제지만, 좌표값이 2차원 배열을 벗어날 경우 건너편으로 이동한다는 점이 조금 다르다고 할 수 있다. 그래서 다음 좌표값을 사용할 때 좌표값을 변환해주는 함수를 사용하여 탐색을 이어나갔다.
그리고 첫 풀이 땐 DFS로 접근했었는데, stack size exceeded
오류가 발생했다. 재귀가 너무 많이 발생하여 call stack이 버티지 못하는것으로 판단되어, BFS로 방법을 바꿔 queue
를 사용했다. queue
또한 시간복잡도를 고려하여 queue index
를 따로 만들어 shift()
대신 사용했다.
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../ex.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const [H, W] = input.shift().split(" ").map(Number);
const map = input.map((item) => item.split(" ").map(Number));
let answer = 0;
const move = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
const queue = [];
let queueIdx = 0;
function bfs() {
while (queueIdx !== queue.length) {
const [h, w] = queue[queueIdx];
queueIdx++;
for (let mv of move) {
const [nextX, nextY] = [w + mv[0], h + mv[1]];
const [convertX, convertY] = convert(nextX, nextY, W, H);
if (map[convertY][convertX] === 0) {
map[convertY][convertX] = 1;
queue.push([convertY, convertX]);
}
}
}
}
function convert(x, y, w, h) {
if (x < 0) return [w - 1, y];
if (x >= W) return [0, y];
if (y < 0) return [x, h - 1];
if (y >= H) return [x, 0];
return [x, y];
}
for (let h = 0; h < H; h++) {
for (let w = 0; w < W; w++) {
if (map[h][w] === 0) {
answer++;
map[h][w] = 1;
queue.push([h, w]);
bfs();
}
}
}
console.log(answer);