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");
}
}