문제
직사각형 모양의 판에 치즈가 놓여 있다. 치즈의 외부 공기와 맞닿은 면의 개수만큼 1시간마다 녹는다. 치즈가 전부 녹을 때까지 걸린 시간과, 모두 녹기 한 시간 전에 남아 있는 치즈 조각 수를 출력한다. 판의 가장자리에는 치즈가 없다고 보장된다.
입력
- 첫째 줄: 행의 수 N, 열의 수 M (1 이상 100 이하)
- 다음 N줄: 0(공기) 또는 1(치즈)로 이루어진 M개의 값
출력
- 첫째 줄: 치즈가 모두 녹는 데 걸리는 시간
- 둘째 줄: 모두 녹기 한 시간 전에 남아 있던 치즈 조각 수
예제
| 입력 | 출력 |
|---|---|
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 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 | 4 6 |
풀이
외부 공기(0,0)에서 DFS로 탐색하여 외부 공기와 접한 치즈를 찾아 녹이는 시뮬레이션이다. 치즈가 없어질 때까지 반복하며 마지막 직전 치즈 수를 기록한다.
check()함수로 치즈가 남아 있는지 확인하고, 직전 단계에서 녹은 치즈 수(cnt)를 저장한다.- (0,0)에서 DFS를 시작하여 외부 공기와 연결된 모든 빈 칸을 탐색한다.
- DFS 중 치즈 칸(값=1)을 만나면 해당 칸을 녹을 예정(값=2)으로 표시하고
cnt를 증가시킨다. check()함수에서 값=2인 칸을 0으로 변환하여 실제로 녹인다.- 치즈가 없어질 때까지 반복하고 경과 시간과 마지막
cnt를 출력한다.
핵심 아이디어: 외부 공기 판별은 (0,0)에서 시작하는 DFS/BFS로 가능하다. 내부 공기(치즈 내부 구멍)는 (0,0)에서 접근 불가능하므로 자동으로 제외된다. 값을 2로 임시 표시하여 같은 라운드에 이미 녹은 치즈가 다시 녹는 것을 방지한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day108BOJ2636치즈 {
static int N, M, cnt, ans;
static int[] dr = { -1, 0, 1, 0 }, dc = { 0, 1, 0, -1 };
static int[][] map;
static boolean[][] visit;
public static void main(String[] args) throws NumberFormatException, IOException {
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];
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());
}
visit = new boolean[N][M];
for (ans = 0; check(); ans++) {
for (boolean[] arr : visit) {
Arrays.fill(arr, false);
}
visit[0][0] = true;
cnt = 0;
dfs(0, 0);
}
System.out.println(ans + "\n" + cnt + "\n");
br.close();
}
public static void dfs(int r, int c) {
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (index(nr, nc))
continue;
if (!visit[nr][nc]) {
visit[nr][nc] = true;
if (map[nr][nc] == 1) {
map[nr][nc] = 2;
cnt++;
} else
dfs(nr, nc);
}
}
}
public static boolean check() {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (map[i][j] == 2)
map[i][j] = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (map[i][j] == 1)
return true;
return false;
}
private static boolean index(int dr, int dc) {
return dr < 0 || dc < 0 || dr >= N || dc >= M;
}
}복잡도
- 시간: O(T × NM) — T는 치즈가 녹는 라운드 수
- 공간: O(NM)