반응형
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point{
int x, y;
Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
}
public class Main {
static int dx[] = {1,0,-1,0};
static int dy[] = {0,1,0,-1};
static int map[][] = new int[101][101];
static Queue<Point> Q = new LinkedList<>();
static Queue<Point> willDisappear = new LinkedList<>();
static boolean isContact(int x, int y){
int cnt = 0;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || nx>n || ny<0 || ny>m) continue;
if(map[nx][ny]==-1){
cnt++;
}
}
if(cnt>=2) return true;
else return false;
}
static int n,m;
static void spreadAir(){
while(!Q.isEmpty()){
Point cur = Q.poll();
for(int i=0; i<4; i++){
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx<0 || nx>n || ny<0 || ny>m) continue;
if(map[nx][ny]==0){
map[nx][ny] = -1;
Q.add(new Point(nx, ny));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=0; i<n; i++){
for(int j=0;j<m; j++){
map[i][j] = sc.nextInt();
}
}
Q.add(new Point(0,0));
Q.add(new Point(0,m-1));
Q.add(new Point(n-1,0));
Q.add(new Point(n-1,m-1));
spreadAir();
int ans = 0;
while(true){
boolean flag = false;
for(int i=0; i<n; i++){
for(int j=0;j<m; j++){
if(map[i][j] == 1){
flag = true;
if(isContact(i,j)){
willDisappear.add(new Point(i,j));
}
}
}
}
if(flag==false) break;
while(!willDisappear.isEmpty()){
Point curr = willDisappear.poll();
map[curr.x][curr.y] = -1;
Q.add(curr);
}
spreadAir();
ans++;
}
System.out.println(ans);
}
}반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 1946번 : 신입사원 - Java fastio, Arraylist , Collections.sort (0) | 2022.05.24 |
|---|---|
| 백준 14950번: 정복자 prim 알고리즘 - Java (0) | 2022.05.22 |
| 백준 4803번 : 트리 - java DFS풀이와 Union & Find 풀이 (0) | 2022.04.30 |
| 백준 2696번 : 중앙값 구하기 Java (0) | 2022.04.23 |
| 백준 2096번 내려가기 C++ (0) | 2022.04.03 |
