(JAVA) [BOJ]백준 2638번, 치즈
- -
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
2638, 치즈
📌 난이도 : Gold 3
📌 알고리즘 : DFS & BFS
이번 문제는 골드 3의 난이도지만 그렇게 어려운 문제는 아니였다. 외부공기와 외부공기가 유입되지 않는 구간만 잘 체크하면 된다! 문제를 잘 읽어보면 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다 는 말이 있다. 그렇다면 치즈가 아닌 공기가 유입될 수 있는 지역에서 DFS 로 모든 공기를 탐색하면 치즈가 있는 구간을 제외하고는 공기의 유입이 되지 않는 구역으로 정해진다. 이것을 유념해서 문제를 풀이해보자.
🧩 프로세스
📚 초기화 및 선언
: 다른 DFS & BFS 풀이들과 비슷하지만 여기서 int[][] Accessable 를 추가로 설정하여 유입되지 않는 구간을 분별한다.
📚 탐색
: 우선 공기가 유입되지 않는 구간을 구해야 한다. 이를 구하는 메서드 makeNotAccessArea() 를 생성해준다. 이는 위에서 설명한 것처럼 제일 빠른 공기의 좌표를 기반으로 BFS 진행하여 지역을 구한다.
public static void makeNotAccessArea() {
Accessable = new boolean[N][M];
Queue<Integer> Q = new LinkedList<>();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
// 1회 탐색
if(map[i][j] == 0) {
Q.add(j);
Q.add(i);
break;
}
}
}
while(!Q.isEmpty()) {
int x = Q.poll();
int y = Q.poll();
for(int k=0; k<4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(Accessable[ny][nx]) continue;
if(map[ny][nx] == 1) continue;
Q.add(nx);
Q.add(ny);
Accessable[ny][nx] = true;
}
}
}
Accessble 의 값이 false이면 공기의 유입이 되지 않는 지역임을 의미한다. 그 후에 DFS 를 통해 치즈의 구역을 탐색하며 치즈를 지울 수 있는가 를 판단하는 check() 메서드를 설계한다. 예외조건을 통과하여 공기와 3면이 닿아있는 지를 판단한다.
// 공기와 3면 이상 닿아있는가
public static boolean check(int x, int y) {
int CNT = 0;
for(int k=0; k<4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(map[ny][nx] == 1) continue;
if(!Accessable[ny][nx]) continue;
CNT++;
}
return CNT >= 2;
}
뽑은 데이터를 backet (stack) 과 참조하고 이후 로직을 진행하며 cnt 를 늘려가면 된다.
✅ 전체 코드
: Flag 를 체크하며 치즈를 줄여가다가 더 이상 지울 치즈가 없다면 루프를 종료하고 카운트를 출력하면 된다.
DFS & BFS 를 활용한 구현 느낌의 문제여서 재밌었다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[][] map, dir = {{1,0},{-1,0},{0,1},{0,-1}};
static int N, M, ANS;
static boolean[][] Accessable, visited;
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
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());
}
}
int ANS = 0;
while(true) {
boolean deleted = false;
visited = new boolean[N][M];
// 유입되지 않는 지역을 선택
// 공기인 구역에서 DFS 1회 호출 NotAccess = true
// 이후에 치즈인 구역을 제외하면 유입되지 않는 지역!
makeNotAccessArea();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
deleted = true;
DFS(j,i);
}
}
}
if(!deleted) break;
ANS++;
}
System.out.println(ANS);
}
public static void makeNotAccessArea() {
Accessable = new boolean[N][M];
Queue<Integer> Q = new LinkedList<>();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
// 1회 탐색
if(map[i][j] == 0) {
Q.add(j);
Q.add(i);
break;
}
}
}
while(!Q.isEmpty()) {
int x = Q.poll();
int y = Q.poll();
for(int k=0; k<4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(Accessable[ny][nx]) continue;
if(map[ny][nx] == 1) continue;
Q.add(nx);
Q.add(ny);
Accessable[ny][nx] = true;
}
}
}
public static void DFS(int x, int y) {
visited[y][x] = true;
if(check(x, y)) {
map[y][x] = 0;
}
for(int k=0; k<4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(map[ny][nx] == 0) continue;
if(visited[ny][nx]) continue;
DFS(nx, ny);
}
}
// 공기와 3면 이상 닿아있는가
public static boolean check(int x, int y) {
int CNT = 0;
for(int k=0; k<4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(map[ny][nx] == 1) continue;
if(!Accessable[ny][nx]) continue;
CNT++;
}
return CNT >= 2;
}
}
'Algorithm > BOJ' 카테고리의 다른 글
(JAVA) [BOJ]백준 2458번, 키 순서 (0) | 2023.09.21 |
---|---|
(JAVA) [BOJ]백준 14891번, 톱니바퀴 (0) | 2023.09.21 |
(JAVA) [BOJ]백준 1937번, 욕심쟁이 판다 (0) | 2023.09.04 |
(JAVA) [BOJ]백준 1167번, 트리의 지름 (0) | 2023.08.31 |
(JAVA) [BOJ]백준 14502번, 연구소 (0) | 2023.08.26 |
소중한 공감 감사합니다