[백준] 13565 침투 - DFS(깊이우선탐색) + BFS(넓이우선탐색) JAVA

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

코드설명

DFS(깊이우선탐색) + BFS(넓이우선탐색) 을 활용합니다.

 

두가지 방식 모두 가능하다만, DFS로 진행했습니다.

가장 맨 위의 행 matrix[0][i] 를 돌면서 전류가 흐를 수 있는곳부터 시작하여 맨 아래 matrix[N-1][i]에 도달할 수 있는지를 체크하면 됩니다.

만약 도달할 수 있다면 "YES"를 출력합니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P;
	static int answer = 0;
	static int[][] matrix;
	static int[] dx = { -1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		matrix = new int[M][N];
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=0;j<N; j++) {
				matrix[i][j] = str.charAt(j) - '0';
			}
		}

		for(int i=0;i<N;i++) {
			boolean[][] visited = new boolean[M][N];
			if(visited[0][i] == false && matrix[0][i] == 0) {
				visited[0][i] = true;
				if(isEnergyGoUpToDown(0, i, visited) > 0) {
					System.out.println("YES");
					return ;
				}
			}
		}
		System.out.println("NO");
	}
	
	static int isEnergyGoUpToDown(int r, int c, boolean[][] visited) {
		if(r == M-1) return 1;
		int ret = 0;
		for(int dir = 0; dir < 4; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
			if(visited[nr][nc] == true) continue;
			if(matrix[nr][nc] == 1) continue;
			visited[nr][nc] = true;
			ret += isEnergyGoUpToDown(nr, nc, visited);
		}
		return ret;
	}
	
}