[백준 gold5] 도넛 행성

준겸이는 $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$ 

예제 입력 1

5 6
1 1 1 1 1 1
1 0 0 0 1 1
1 1 1 1 0 0
1 1 1 1 0 0
1 1 1 1 1 1

예제 출력 1

2

예제 입력 2

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

2

직사각형 격자로 보이지만 실제로는 한 바퀴를 돌아 이동할 수 있는 도넛 모양이기 때문에, 빈 영역의 개수는 두 개이다.

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((r) => r.split(" ").map(Number));
// 구조 분해 할당으로 입력 받아오니 한 줄이면 끝!
const [[N, M], ...planet] = input;

function dfs(x, y) {
// 재귀가 안 된다니 stack과 반복문을 사용하자
  const stack = [[x, y]];
  // 방문 처리
  planet[x][y] = 1;

  while (stack.length) {
  // dfs이므로 stack에서 꺼내옴
    const [x, y] = stack.pop();

 // stack에 nx, ny를 push하고 방문처리를 하는 push 함수를 만듦
    function push(nx, ny) {
      if (planet[nx][ny] === 0) {
        stack.push([nx, ny]);
        planet[nx][ny] = 1;
      }
    }

// 본격 깊이 우선 탐색 시작하는 조건문들.
    if (x > 0) push(x - 1, y);
    if (x < N - 1) push(x + 1, y);
    if (y > 0) push(x, y - 1);
    if (y < M - 1) push(x, y + 1);
    if (x === 0) push(N - 1, y);
    if (x === N - 1) push(0, y);
    if (y === 0) push(x, M - 1);
    if (y === M - 1) push(x, 0);
  }
}

// planet[i][j] === 0일 때만 함수를 호출
let count = 0;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (planet[i][j] === 0) {
      dfs(i, j);
      count++;
    }
  }
}
// 함수 호출한 횟수가 곧 답이 된다.
console.log(count);

이 문제는 쇼미더코드에 나왔었다. 그 때 알고리즘 시작한지 1~2달 되었을 때 그냥 문제 구경해보려고 참여했었는데 역시 구경 잘 하고 나왔었다. ^^

근데 이 문제 언제 백준에 들어왔지? 반가워서 다시 풀어보았다.
처음에 재귀로 풀었다가 StackSizeExceeded 오류를 만났다.
헉 나는 dfs 풀 때는 항상 재귀로 풀었는뎁쇼? 새로운 시도를 해보자. 반복문으로 영차영차 바꿔보았다!

조건문 부분이 제일 어려웠다..
만약 x,y가 둘 다 0번째 또는 끝번째 인덱스가 아니라면? 간단히 동서남북의 좌표만 stack에 push 해주면 된다.

if (x > 0) push(x - 1, y);
if (x < N - 1) push(x + 1, y);
if (y > 0) push(x, y - 1);
if (y < M - 1) push(x, y + 1);

하지만 현재 좌표가 예를 들어 (0,3)이라면?

if (x < N - 1) push(x + 1, y);
if (y > 0) push(x, y - 1);
if (y < M - 1) push(x, y + 1);
if (x === 0) push(N - 1, y);

위의 4개 조건문에 의해 stack에 (1,3), (0,2), (0,4), (6,3)이 stack에 들어가는 것이다. 이렇게 하면 남, 서, 동, 같은 열의 맨 아랫줄 원소가 stack에 들어간다.

그럼 다음으로는 stack에서 (6,3)을 꺼내오겠지?

if (x > 0) push(x - 1, y);
if (y > 0) push(x, y - 1);
if (y < M - 1) push(x, y + 1);
if (x === N - 1) push(0, y);

이렇게 3가지 조건에 의해서 (5,3), (6,2), (6,4), (0,3)이 stack에 들어가는 것이다. (0,3)은 이미 방문 처리 되었으니 무시될 것이고, 각각 stack에서 꺼내면 동, 서, 북 순으로 탐험이 가능하다.

if문이 8개나 되어서 머리가 아프지만, 나름 push function을 이용하여 코드를 간결하게 잘 줄인 것 같다. 그리고 원래 bfs나 dfs 풀 때 조건에 안맞으면 continue하는 방식을 더 많이 사용했는데, if문으로 조건에 맞는 경우에만 들어오는 방식을 사용하니 더 깔끔한 것 같다.

아 그리고 하나 더! input 처리할 때 원래 shift() 사용해서 첫 줄의 행, 열 크기 등의 정보를 받아왔었는데, 구조분해 할당을 쓰니 완전 깔끔쓰하다.

어렵지만 재밌는 문제이다!! 다른 문제도 또 풀어보자. 화이팅~!~!