[BOJ][⚪2][백준#13565] 침투

문제 출처

BAEKJOON Online Judge #13565

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다. 김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

(a) The current percolates. (b) The current does not percolate.

예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.

입력

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다. 그렇지 않으면 NO를 출력한다.

예제

예제 1

입력

5 6
010101
010000
011101
100011
001011

출력

NO

예제 2

입력

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

출력

YES

My Sol

const fs = require("fs");
const input = fs
  .readFileSync('/dev/stdin')
  .toString()
  .split("\n")
  .map((a) => a.trim());

// 상하좌우 탐색
const delta = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];
const search = (i, j) => {
  for ([di, dj] of delta) {
    const [si, sj] = [i + di, j + dj];
    if (si < 0 || si >= I || sj < 0 || sj >= J) continue;
    if (mat[si][sj]) continue;
    mat[si][sj] = 2;
    if (si === I - 1) return true;
    if (search(si, sj)) return true;
  }
};

let ans = "NO";
const [I, J] = input[0].split(" ").map(Number);
const mat = [];
for (let i = 0; i < I; i++) {
  mat.push(input[i + 1].split("").map(Number));
}

for (let j = 0; j < J; j++) {
  if (!mat[0][j]) {
    mat[0][j] = 2;
    if (search(0, j)) {
      ans = "YES";
      break;
    }
  }
}

console.log(ans);

전형적인 DFS/BFS문제였다. 나는 DFS를 활용했다.

목표 : 0번 행부터 시작해서 (I-1)행에 도달하면 ‘YES’, 아니면 ‘NO’이다.

1. 2차원 배열 입력을 처리한다.
2. 0번 행의 각 열의 값들을 확인한다.
3. 1이라면 PASS, 0이라면 해당 좌표부터 탐색을 시작한다.
4. 상하좌우의 좌표에 대해 범위를 벗어나면 PASS
5. 1 또는 다녀갔던 경로(2)라면 PASS
6. 모든 필터링을 지나쳤으므로 해당 좌표에 2를 표시하고 다시 search함수를 불러온다.
7. 해당 탐색 좌표부터 상하좌우를 다시 탐색한다.
8. 이때 맨 아래 행(I-1)에 도달하면 전류가 통하는 것이므로 true를 return한다.
9. 맨 처음에 호출한 search 함수에 대해 true를 return하면 ans를 바꾸고 break
10. ans를 출력한다.
11. 즉, 0행의 모든 j열에서 true를 반환하지 않는다면 ans는 NO, 한 번이라도 true를 반환하면 ans는 YES이다.

결과

맞았습니다!!

모범답안

출처

const line = require("fs").readFileSync("/dev/stdin", "utf8");
let input = line.trim().split("\n");

const [n, m] = input.shift().split(" ").map(Number);

const board = Array.from({ length: n }, () => input.shift().split(""));

for (let i = 0; i < board[0].length; i++) {
  if (board[0][i] === "0") {
    board[0][i] = "2";
    if (dfs(i, 0)) return console.log("YES");
  }
}

function dfs(x, y) {
  if (y === n - 1) {
    return true;
  } else {
      if (y !== n - 1 && board[y + 1][x] === "0") {
    board[y + 1][x] = "2";
    if (dfs(x, y + 1)) return true;
  }
  if (x !== m - 1 && board[y][x + 1] === "0") {
    board[y][x + 1] = "2";
    if (dfs(x + 1, y)) return true;
  }
  if (y !== 0 && board[y][x - 1] === "0") {
    board[y][x - 1] = "2";
    if (dfs(x - 1, y)) return true;
  }
  if (y !== 0 && board[y - 1][x] === "0") {
    board[y - 1][x] = "2";
    if (dfs(x, y - 1)) return true;
  }
  }
}

console.log("NO");

메모리 사용량과 연산시간이 각각 절반정도 되는 코드를 분석해보려 한다.

방식은 비슷하지만 차이점이 몇 있다.

1. 우선 나는 각 숫자형 문자를 .map(Number)로 숫자로 바꾸었는데, 이 분은 그대로 문자형으로 사용하셨다.

2. 나는 delta에 대해 forEach를 하며 si, sj를 매번 선언/할당해주었지만, 이 분은 상하좌우의 delta에 대해 어떻게 보면 하드코딩한 것 같다.

아마 2번에서 차이를 보인 것 같은데 효율적인 코드와 가시성 있는 코드에서의 선택이 참 애매한 것 같다. 아무튼 도움이 되는 코드였다.

2차원 배열 입력 Tip

const board = Array.from({ length: n }, () => input.shift().split(""));

input에서 행을 뽑아내어 한 문자씩 잘라 넣는 작업을 n번 실행한다는 개념 같다.