[Java] 백준 13165번 침투

문제

13565번: 침투

입력

• 첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

출력

• 바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.
• 그렇지 않으면 NO를 출력한다.

입력 예제

5 6
010101
010000
011101
100011
001011

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

출력 예제

NO

YES

문제 풀이

• (0,m)의 값이 0일 때 dfs 탐색을 진행하여 전류를 흘려보낸다.
• 전류가 공급되는 격자일 때 (주어진 배열의 값이 0일 때) 재귀적으로 상하좌우 탐색
  • 출발지가 바뀔 때 마다 방문 배열을 초기화해서 전류를 처음부터 탐색 해야한다고 생각했으나, 어떻게든 열의 값이 0일 때 출발하여 n - 1에 도달만 하면 되므로, 방문 배열을 매 탐색마다 초기화 할 필요 X, 또한 이미 방문한 곳은 더 이상 방문하지 않도록 처리
• n - 1에 도달했다면, 전류가 침투될 수 있는 경우이므로, answer 값을 YES로 바꾸고 리턴한다.

코드

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;
    static int m;
    static int[][] arr;
    static boolean[][] possible;
    
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    
    static String answer = "NO";
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        possible = new boolean[n][m];
        
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }
        
//        print(arr);
        for (int i = 0; i < m; i++) {
            if (arr[0][i] == 0) {
                dfs(0,i);
            }
        }
        
        System.out.println(answer);
    }

    private static void dfs(int i, int j) {
        
    	possible[i][j] = true;
    	
        // basis part
        if (i == n - 1) {
        	answer = "YES";
            return;
        }
        
        // inductive part
        for (int d = 0; d < 4; d++) {
            int y = i + dy[d];
            int x = j + dx[d];
            if (0 <= y && y < n && 0 <= x && x < m && !possible[y][x] && arr[y][x] == 0) {
               dfs(y,x);
            }
        }
    }

    private static void print(int[][] arr) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
        
    }

}