[BOJ] 13565 침투 - JAVA

1. 문제

13565번: 침투

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

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

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

---

2. 풀이

BFS로 풀었다.

1.  입력값을 전부 char 배열로 바꿔서 map에 저장한다.

2.  map[0]을 탐색해서 그 중에 흰 칸('0')만 큐에 넣는다.

3.  큐에서 현위치를 뽑아가면서 그 다음 가능한 자리를 탐색하고 '1'로 변경한 뒤 큐에 넣는다. 현 위치를 뽑았을 때 M번째 줄이라면 YES를 출력하고 프로그램을 완전히 종료한다.

4.  while 반복문 안에서 return 되지 않고 반복문이 종료될 때까지 프로그램이 실행중이라면 전류가 안쪽까지 침투할 수 없는 경우이므로 NO를 출력하고 끝낸다.

import java.io.*;
import java.util.*;

public class BOJ_13565_침투 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int M = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(st.nextToken());
      Queue<int[]> queue= new ArrayDeque<>();
      char[][] map = new char[M][N];
      for(int i=0;i<M;i++){
         map[i] = in.readLine().toCharArray();
      }
      for(int j=0;j<N;j++){
         if(map[0][j]=='0') {
            queue.offer(new int[]{0,j});
            map[0][j] = '1';
         }
      }

      int[] pos;
      int[][] deltas = {{1,0},{-1,0},{0,-1},{0,1}};
      while(!queue.isEmpty()){
         pos = queue.poll();
         if(pos[0] == M-1){
            System.out.println("YES");
            return;
         }

         for(int d=0;d<4;d++){
            int ni = pos[0]+deltas[d][0];
            int nj = pos[1]+deltas[d][1];
            if(ni>=0 && ni<M && nj>=0 && nj<N && map[ni][nj]=='0'){
               map[ni][nj]='1';
               queue.offer(new int[]{ni,nj});
            }
         }
      }

      System.out.println("NO");
   }
}

---

3. 결과