OJ
[BOJ] 27211 도넛 행성 (JAVA)
P3PP4
2023. 1. 20. 10:00
https://www.acmicpc.net/problem/27211
27211번: 도넛 행성
준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수
www.acmicpc.net
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 {
int[] dr = { -1, 0, 1, 0 };
int[] dc = { 0, 1, 0, -1 };
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
} // end of input
boolean[][] visited = new boolean[N][M];
Queue<Pos> q = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(map[i][j] == 0 && !visited[i][j]) {
q.offer(new Pos(i, j));
visited[i][j] = true;
cnt++;
while(!q.isEmpty()) {
Pos p = q.poll();
for (int dir = 0; dir < 4; dir++) {
int nr = p.row + dr[dir];
int nc = p.col + dc[dir];
if(nr < 0) nr = N - 1;
else if(N <= nr) nr = 0;
if(nc < 0) nc = M - 1;
else if(M <= nc) nc = 0;
if(map[nr][nc] == 0 && !visited[nr][nc]) {
visited[nr][nc] = true;
q.offer(new Pos(nr, nc));
}
}
}
}
}
}
System.out.println(cnt);
}
static class Pos {
int row, col;
public Pos(int row, int col) {
this.row = row;
this.col = col;
}
}
}