BOJ 2638 치즈(Java)
문제 탐색하기
- N×M의 모눈종이 위에 아주 얇은 치즈가 그림과 같이 표시되어 있다.
- 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다.
- 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다.
- 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다.
-
따라서 그림과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
- 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.
- 치즈가 모두 녹아 없어지는 데 걸리는 시간을 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (3 ≤ N, M ≤ 100)이 주어진다.
- 이후 N개의 줄에는 모눈종이의 각 칸에 대한 정보를 나타내는 0 이상 1 이하의 정수가 주어진다.
- 0은 치즈가 없는 칸을 나타내고, 1은 치즈가 있는 칸을 나타낸다.
출력
- 치즈가 모두 녹아 없어지는 데 걸리는 시간을 출력한다.
예제 입력
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
예제 출력
4
코드 설계하기
구현 방법
- 외부 공기 영역 탐색 (BFS)
- (0,0)에서 시작하여 BFS로 외부 공기(0)를 탐색
- visited 배열에 외부 공기 영역을 표시
- 이 과정으로 치즈 내부의 공기와 외부 공기를 구분
- 녹을 치즈 찾기 (BFS)
- 모든 치즈(1)에 대해 주변 4방향을 확인
- 외부 공기(visited가 true인 0)와 접촉한 면의 수를 세어 2개 이상이면 녹을 치즈로 표시
- 녹을 치즈가 없으면 종료
- 치즈 녹이기
- 녹을 치즈를 모두 찾은 후 한 번에 녹임
- 시간 증가
시간 복잡도
- 외부 공기 영역 탐색: O(N*M)
- 녹을 치즈 찾기: O(N*M)
- 치즈 녹이기: O(녹을 치즈의 수)
- 전체 시간 복잡도: O(T * 3N * M)
- T: 치즈가 모두 녹는데 걸리는 시간 (최대 N/2)
- N X M: 격자의 크기 (최대 100*100)
- 실제 최악의 경우: O(50 * 3 * 10,000) = O(1,500,000)
이므로 시간 제한 내에 충분히 수행이 가능하다.
시도 회차 별 수정사항(Optional)
- 첫 번째 시도
- 한 번의 BFS로 외부 공기와 치즈를 동시에 처리하려고 시도
- 문제점:
- 치즈 내부의 공기와 외부 공기를 구분하지 못함
- 치즈가 녹는 조건을 정확히 판단하지 못함
- 두 번째 시도 (정답)
- 외부 공기 영역 탐색과 녹을 치즈 찾기를 분리
- 매 시간마다
visited배열을 새로 생성하여 외부 공기 영역을 정확히 구분 - 치즈가 녹는 조건을 정확히 판단하여 구현
정답 코드 (Java)
package BFS;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class b2638 {
private static int N, M, cnt = 0;
private static boolean[][] visited;
private static int[][] map;
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[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());
}
}
while (true) {
// 외부 공기 영역 표시
boolean[][] visited = new boolean[N][M];
Queue<int[]> airQueue = new LinkedList<>();
airQueue.add(new int[]{0, 0});
visited[0][0] = true;
while (!airQueue.isEmpty()) {
int[] current = airQueue.poll();
int x = current[0], y = current[1];
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (map[nx][ny] == 0 && !visited[nx][ny]) {
visited[nx][ny] = true;
airQueue.add(new int[]{nx, ny});
}
}
}
// 녹을 치즈 찾기
Queue<int[]> meltQueue = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1) {
int airCount = 0;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (map[nx][ny] == 0 && visited[nx][ny]) {
airCount++;
}
}
if (airCount >= 2) {
meltQueue.add(new int[]{i, j});
}
}
}
}
// 녹을 치즈가 없으면 종료
if (meltQueue.isEmpty()) break;
// 치즈 녹이기
while (!meltQueue.isEmpty()) {
int[] melt = meltQueue.poll();
map[melt[0]][melt[1]] = 0;
}
cnt++;
}
System.out.println(cnt);
}
}
Leave a comment