백준 13565번 침투 (java)

[Silver II] 침투 - 13565

문제 링크

성능 요약

메모리: 22900 KB, 시간: 220 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 11일 01:19:43

문제 설명

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

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

 

입력

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

출력

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

그렇지 않으면 NO를 출력한다.

 

풀이

상하좌우를 돌아보며 0을 발견하면 해당 칸으로 이동하면 된다.

그렇게 계속 이동하다 마지막 행에 도달하면 return을 시키면 된다.

 

전체 코드

public class Main {

    static int N, M, x[][], check = 0;
    static int X[] = {0,0,1,-1}, Y[] = {1,-1,0,0};
    static boolean visited[][];

    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N][M];

        x = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                x[i][j] = line.charAt(j) - '0';
            }
        }

        for(int  i = 0 ;i<M;i++){
            if(x[0][i] == 0){
                dfs(0,i);
                if(check == 1){
                    bw.write("YES");
                    bw.flush();
                    return;
                }
            }

        }


        bw.write("NO");
        bw.flush();



    }

    public static void dfs(int now, int xx){
        if(now == N-1){
            check = 1;
            return;
        }


        for(int  j = 0; j<4;j++){
            int x1 = xx + X[j];
            int y1 = now + Y[j];
            if(x1>=0 && x1 < M && y1 >= 0 && y1 < N){
                if(x[y1][x1] == 0 && !visited[y1][x1]){
                    visited[y1][x1] = true;
                    dfs(y1,x1);
                    if(check == 1){
                        break;
                    }
                }
            }
        }

    }



}