백준_침투_13565

침투

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

예를 들어, 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

예제 출력 1

NO

예제 입력 2

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2

YES

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [M, N] = input[0].split(' ').map(Number); // MXN 격자
let grid = []; // 격자

// 0: 흰색(전류 통할 있는 물질), 1: 검은색(전류 통하지 않는 물질)
for (let i = 1; i <= M; i += 1) grid.push(input[i].split('').map(Number));

// 상하좌우
const dx = [-1, 0, 1, 0];
const dy = [0, -1, 0, 1];

let result = false; // 결과

let visited = Array.from({ length: M }, () => new Array(N).fill(false)); // 방문 표시 배열

const dfs = (x, y) => {
  for (let i = 0; i < 4; i += 1) {
    const [nx, ny] = [x + dx[i], y + dy[i]]; // 다음 칸으로 이동
    if (nx < 0 || nx >= M || ny < 0 || ny >= N || grid[nx][ny] === 1) continue; // 범위 벗어나는 경우
    // 끝에 도달하면 전투 가능
    if (nx === M - 1) {
      result = true;
      return;
    }
    // ※ 이미 방문한 곳은 더이상 전류가 흐를 수 없으므로 방문 표시 해제 안해도됨!
    if (!visited[nx][ny]) {
      visited[nx][ny] = true; // 방문 표시
      dfs(nx, ny); // dfs 수행
      if (result) return; // 전투 가능하므로 더이상 dfs 수행 X
    }
  }
};

// 바깥쪽에서 시작할 수 있는 N개
for (let i = 0; i < N; i += 1) {
  if (result) break;
  // 0(흰색)일 때만 전류 흐를 수 있으니까 그떄만 dfs 수행
  if (grid[0][i] === 0) {
    visited[0][i] = true;
    dfs(0, i);
  }
}

result ? console.log('YES') : console.log('NO');

풀이 및 해설

• 구하고자 하는 것 = 바깥쪽에서 흘려준 전류가 안쪽까지 침투할 수 있는지 판단

  • 섬유 물질 2차원 MXN 격자
  • 위쪽 ⇒ 바깥쪽, 아래쪽 ⇒ 안쪽
  • 검은색(1) ⇒ 전류 차단 물질, 흰색(0) ⇒ 전류 통하는 물질
  • 전류는 가장 바깥쪽 흰색 격자들에 공급, 상하좌우로 인접한 흰색 격자들로 전달가능

• dfs 이용

  • dx=[-1,0,1,0] , dy=[0,1,0,-1] ⇒ 상하좌우 방향
  • 만약 범위 벗어나거나 다음칸이 1이고, 방문한 곳은 dfs 수행 X
  • 현재 위치의 Y값이 M이라면 도달 가능하므로 YES 출력
  • result가 true가 된다면 더이상 dfs 수행 안해도됨!

• 시간초과 해결에서 막혔던 부분

  visited[nx][ny]=false; 로 dfs 수행이 끝나면 방문 표시를 풀어줬음

  ⇒ 다음 바깥쪽 영역에서 방문 할 수 있으므로

  근데, 어차피 해당 부분은 전류가 흐를 수 없는 공간이므로 방문 표시 해제를 안해도됨!