문제

문제 링크

준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다.

준겸이는 본인의 집이 있는 위치를 기준으로 삼아 $(0,0)$이라고 표시하기로 했다. 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸 걸어가면, 위치 $(0,1)$에 도달할 것이다. 마찬가지로 아래로 한 칸 걸어가면, 위치 $(1,0)$에 도달할 것이다. 준겸이가 $(0,0)$에서 $M$칸 오른쪽으로 걸어가면, 한 바퀴를 돌아 다시 원래 자리로 되돌아오게 된다. 비슷하게 $(0,0)$에서 $N$칸 아래로 걸어가면, $(0,0)$으로 돌아오게 된다. 행성은 연결되어 있기 때문에, 준겸이가 $(0,0)$에서 왼쪽으로 한 칸 걸어가면 위치 $(0,M-1)$에 도달할 것이다. 마찬가지로 준겸이가 $(0,0)$에서 위로 한 칸 걸어가면 $(N-1, 0)$에 도달하게 된다.

준겸이는 행성을 탐험하려고 한다. 만약 준겸이가 비어 있는 어떤 칸 $A=(p_1,q_1)$에서 시작해, 숲에 막히지 않고 비어 있는 칸 $B=(p_2,q_2)$에 도달할 수 있다면 $A$와 $B$는 같은 구역이다. 반대로, 도달할 수 없다면 $A$와 $B$는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.

입력

첫 번째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $N \times M$개의 칸에 대한 정보가 주어진다. 두 번째 줄에서부터 $i$번째 줄에 주어지는 $j$번째 정수는 칸 $(i-1, j-1)$에 대한 정보이다. 만약 0이라면 비어 있는 것이고, 1이라면 숲으로 막혀 있는 것이다.

출력

탐험할 수 있는 구역의 개수를 출력한다.

제한

• $2 \le N \le 1\,000$ 
• $2 \le M \le 1\,000$ 

예제 입력

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);