Baekjoon 13565 침투 JAVA

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를 출력한다.

풀이

문제가 복잡해보이지만 간단한 문제이다.

입력되는 값은 0으로 전류가 통하는 격자와 1로 전류가 통하지 않는 격자 2개의 종류가 입력이 된다.

첫 번째 행의 0격자에서 BFS혹은 DFS를 이용해서 가장 마지막 행의 0까지 이어진다면 전류가 흐르는 것이다.

BFS를 이용해서 탐색을 할 때 이미 탐색한 격자를 두번 체크하지 않기 위해서 체크하는 값을 2로 변경하여 동일한 격자를 2번이상 탐색하지 않도록한다.

Queue안에 값이 있을때까지 반복해서 탐색을 하면 연결이 되어있는 모든 격자들이 2로 바뀌게된다.

모든 탐색할 수 있는 위치들이 끝난다면 마지막 행을 탐색하면서 2로 되어있다면 첫 행부터 마지막 행까지 연결되어 있다는 것이기에,

YES를 출력한다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m=Integer.parseInt(st.nextToken()), n=Integer.parseInt(st.nextToken());
		char [][] map = new char [m][n];
		for(int i=0;i<m;i++)
			map[i] = br.readLine().toCharArray();
		
		Queue<int []> q = new LinkedList<>();
		for(int i=0;i<n;i++) {
			if(map[0][i]=='0') {
				q.add(new int[] {0,i});
				map[0][i]='2';
			}
		}
		int [] dx={1,-1,0,0}, dy= {0,0,1,-1};
		while(q.size()>0) {
			int [] cur = q.poll();
			int x=cur[0], y=cur[1];
			for(int i=0;i<4;i++) {
				int nx=x+dx[i], ny=y+dy[i];
				if(nx>=0 && nx<m && ny>=0 && ny<n && map[nx][ny]=='0') {
					q.add(new int[] {nx,ny});
					map[nx][ny]='2';
				}
			}
		}
		String ans="NO";
		for(int i=0;i<n;i++){
			if(map[m-1][i]=='2')
				ans="YES";
		}
		System.out.println(ans);
	}
}