OJ

[BOJ] 13565 침투 (JAVA)

P3PP4 2022. 12. 28. 10:00

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

 

13565번: 침투

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

www.acmicpc.net

기본적인 BFS 문제입니다.

맨 윗줄의 0들에서 시작해서 맨 아랫줄 0에 닿을 수 있으면 YES, 아니면 NO를 출력합니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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());
        int N = Integer.parseInt(st.nextToken());
        char[][] arr = new char[M][N];
        boolean[][] visited = new boolean[M][N];
        int[] dr = { -1,  0,  1,  0 };
        int[] dc = {  0,  1,  0, -1 };
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < M; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = line.charAt(j);
                if(i == 0 && arr[i][j] == '0') {
                    q.offer(new int[] { i, j });
                    visited[i][j] = true;
                }
            }
        } // end of input

        while(!q.isEmpty()) {

            int[] now = q.poll();

            if(now[0] == M - 1) {
                System.out.print("YES");
                return;
            }

            for (int dir = 0; dir < 4; dir++) {

                int nr = now[0] + dr[dir];
                int nc = now[1] + dc[dir];

                if(0 <= nr && nr < M && 0 <= nc && nc < N && !visited[nr][nc] && arr[nr][nc] == '0') {

                    q.offer(new int[] { nr, nc });
                    visited[nr][nc] = true;

                }

            }

        }
		
        System.out.print("NO");

    }
	
}