白駿2636号:チーズ
24980 ワード
問題の説明
https://www.acmicpc.net/problem/2636
方法
pseudocode
// -1은 공기, 0은 구멍, 1은 치즈입니다.
while(처음에 치즈가 존재해야 시작할 수 있습니다){
BFS(0,0) // (0,0)에서 도달 가능한 0을 모두 -1로 만듭니다.
for(모든(i,j)를 순회하면서){
// 여기서의 0은 구멍의 의미는 아닙니다. 녹은 치즈를 곧바로 -1로 만들면 다른 치즈의 검사에도 영향을 주기 때문에 0으로 만들었습니다. 알고리즘에 의해 다음 검사부터 -1이 됩니다.
-1과 맞닿은 1을 0으로 만듭니다.
}
for(모든(i,j)를 순회하면서){
-1을 0으로 바꿉니다. // BFS는 (0,0)에서 0을 찾도록 설계되어 있습니다. -1은 인식하지 못하기 때문에 0으로 되돌립니다.
}
if(현재 남아있는 치즈의 개수가 0개면){
break
}else{
남아있는 치즈의 개수를 갱신합니다.
}
}
BFS(){
(0,0)에서 연결된 모든 0을 -1로 바꿉니다.
}
正解
import java.util.*;
class Main {
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int N, M, LastCheeze;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
int[][] board = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int val = sc.nextInt();
board[i][j] = val;
LastCheeze += val;
}
}
int time = 0;
while (LastCheeze!=0) { // 처음부터 치즈가 없다면 실행하지 말아야 합니다.
time++;
BFS(0, 0, board); // (0,0)과 연결된 0은 공기, 그렇지 않은 0은 구멍 // 공기를 모두 -1로 바꿉니다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == 0 || board[i][j] == -1) continue; // 공기나 구멍은 패스합니다.
// 치즈의 4방 중 한 곳이라도 공기(-1)면 해당 치즈가 녹습니다.
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == -1) {
board[i][j] = 0;
break;
}
}
}
}
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == -1) {
board[i][j] = 0; // 다음 BFS를 위해 -1로 바꾼 공기를 0으로 되돌립니다
} else if(board[i][j] == 1){ // 현재 남아있는 치즈의 개수를 샙니다.
cnt++;
}
}
}
if (cnt == 0) { // 남아있는 치즈가 없다면 while문을 종료합니다.
break;
} else {
LastCheeze = cnt;
}
}
System.out.println(time);
System.out.println(LastCheeze);
}
public static void BFS(int x, int y, int[][] board) {
board[x][y] = -1;
int[] temp = { x, y };
Queue<int[]> q = new LinkedList<int[]>();
q.add(temp);
while (!q.isEmpty()) {
int[] now = q.poll();
for (int d = 0; d < 4; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == 0) {
board[nx][ny] = -1;
int[] temp2 = { nx, ny };
q.add(temp2);
}
}
}
}
}
その他
Reference
この問題について(白駿2636号:チーズ), 我々は、より多くの情報をここで見つけました https://velog.io/@qwerty1434/백준-2636번-치즈テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol