백준 | 13565번. 침투 - BFS& DFS 풀이

⬛ 백준 13565번. 침투 - BFS& DFS 풀이

https://www.acmicpc.net/problem/13565

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) BFS 풀이

• 우선 바깥쪽은 0행 위치에서 값이 0인 부분이 될 것이고, 안쪽은 N-1행 위치에서 값이 0인 부분이 될 것이다.
• 이 문제는 0행쪽에 보낸 전류가 쭉 연결이 되어서 안쪽인 N-1행까지 잘 전달이 되었는지 확인하는 문제였다.
• 우선은 BFS로 문제를 풀었다.
• 시작하는 위치는 0행에서 값이 0인 곳을 찾아 BFS를 반복하여 호출하는데 그 호출한 값의 리턴이 true 즉, 밑바닥에 한 번이라도 닿는 게 있으면 YES를 , 밑바닥에 한 번도 닿지 못해서 false가 리턴 되었으면 NO를 출력하면 되는 문제이다.

package to_0908_7;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*백준 13565번 침투 - BFS & DFS 풀이 */
public class Main {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	//BFS
	static boolean BFS(int x, int y) {
		Queue<int[]> Q= new LinkedList<>();
		visited[x][y] = true;
		Q.offer(new int[] {x, y});
		
		while(!Q.isEmpty()) {
			int[] cur = Q.poll();
			//만약 여기서 뽑은 애가 N-1이 된다면 밑마닥까지 닿은 거니까 true 리턴시킴
			if(cur[0] == N-1) return true;
			
			for(int k= 0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx <0 || ny <0 || nx >= N || ny>=M) continue;
				//전류 통하는 0 이 존재한다면 계속 넘비 탐색
				if(!visited[nx][ny] && map[nx][ny] == 0) {
					Q.offer(new int[] {nx, ny});
					visited[nx][ny] = true;
				}
			}
			
		}
		
		
		
		return false;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
	
		map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String tmp = kb.next();
			for(int j=0; j<M; j++) {
				map[i][j] = Character.getNumericValue(tmp.charAt(j));
			}
		}
		
		visited= new boolean[N][M];
		boolean flag = false;
		
		for(int i=0; i<M; i++) {
			if(map[0][i] == 0) {//즉 바깥 라인에서 전류 흐를 수 있는 흰색일 경우 
				if(BFS(0, i)) {
					flag = true;//하나라도 밑바닥까지 전달되는 게 있다면 true
				}
			}
		}
	
		if(!flag) {
			System.out.println("NO");
		}else {
			System.out.println("YES");
		}
	}
}

2) DFS 풀이

• 여기서는 반환을 따로 해주지 않고 정적 변수로 flag를 false로 초기화해둔 뒤 0행의 값이 0인 곳에서 DFS를 모두 호출해주다가 x값이 N-1행에 닿는 곳이 생기게 되면 flag = true로 갱신하도록 해두었다.
• 결과적으로 DFS를 호출해서 안쪽 N-1행까지 쭉 뻗을 수 있다면 YES , 아니라면 NO를 출력하도록 문제를 풀었다.

import java.util.*;

/*백준 13565번 침투 - BFS & DFS 풀이 */
public class Main {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	static boolean flag = false;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	//DFS	
	static void DFS(int x, int y) {
		if(x == N-1) {//깊이 호출하다가 x행이 N-1밑바닥 행이 된다면 
			flag =  true;//여기서 true 리턴하면 되고 
		}
		visited[x][y] = true;
		
		for(int k =0; k<4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx <0 || ny <0 || nx >= N || ny>=M) continue;
			if(!visited[nx][ny] && map[nx][ny] == 0) {
				DFS(nx, ny);
			}
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
	
		map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String tmp = kb.next();
			for(int j=0; j<M; j++) {
				map[i][j] = Character.getNumericValue(tmp.charAt(j));
			}
		}
		
		visited= new boolean[N][M];
		
		for(int i=0; i<M; i++) {
			if(map[0][i] == 0) {//즉 바깥 라인에서 전류 흐를 수 있는 흰색일 경우 
				DFS(0, i);//모두 호출해도 
			}
		}
		if(!flag) {
			System.out.println("NO");
		}else {
			System.out.println("YES");
		}
	}
}