BOJ 2638 - 치즈 | 안성진

문제

BOJ 2638 - 치즈

N×M 격자에 치즈가 놓여 있다. 치즈가 외부 공기와 2면 이상 접촉하면 녹는다. 모든 치즈가 녹는 데 걸리는 시간을 구한다.

격자 가장자리는 항상 공기(빈 칸)이다.
외부 공기: (0, 0)에서 DFS/BFS로 도달 가능한 빈 칸

입력

첫째 줄에 N, M이 주어진다. (2 ≤ N, M ≤ 100)

다음 N줄에 격자 정보가 주어진다. (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 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0

출력:

풀이

핵심 아이디어: 매 시간마다 (0,0)에서 DFS로 외부 공기를 탐색(방문한 빈 칸을 -1로 표시)하고, 치즈 칸의 4방향 중 -1(외부 공기)인 면이 2개 이상이면 녹인다. 이를 반복하여 총 시간을 센다.

단계별 흐름:

초기에 치즈 칸(1)의 위치를 list에 저장하고 총 치즈 수 tot를 센다.
tot > 0인 동안 반복한다:
- ans++(시간 증가)
- dfs(0, 0)으로 외부 공기를 탐색하여 빈 칸을 -1로 마킹한다.
- melt()로 list의 각 치즈 칸 주변 -1 면이 2개 이상이면 해당 칸을 0으로 변경하고 tot--, list에서 제거한다.
치즈를 리스트로 관리하여 반복마다 모든 격자를 순회하지 않고 효율적으로 처리한다.

코드

package com.ssafy.an.day249;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Day202BOJ2638치즈DFS {
	static int N, M, tot = 0, ans = 0;
	static int[][] map;
	static boolean[][] visited;
	static List<int[]> list;
 
	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];
		list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				tot += map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					list.add(new int[] { i, j });
			}
		}
		while (tot > 0) {
			ans++;
			visited = new boolean[N][M];
			dfs(0, 0);
			melt();
		}
		System.out.println(ans);
		br.close();
	}
 
	static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
 
	private static void melt() {
		for (int i = 0; i < list.size(); i++) {
			int r = list.get(i)[0];
			int c = list.get(i)[1];
			int cnt = 0;
			for (int dir = 0; dir < 4; dir++) {
				int nr = r + dr[dir];
				int nc = c + dc[dir];
				if (map[nr][nc] == -1)
					cnt++;
			}
			if (cnt > 1) {
				map[r][c] = 0;
				tot--;
				list.remove(i--);
			}
		}
	}
 
	private static void dfs(int r, int c) {
		visited[r][c] = true;
		map[r][c] = -1;
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
 
			if (index(nr, nc))
				continue;
			if (visited[nr][nc])
				continue;
			if (map[nr][nc] == 1)
				continue;
			dfs(nr, nc);
		}
	}
 
	private static boolean index(int r, int c) {
		return r < 0 || c < 0 || r >= N | c >= M;
	}
}

복잡도

시간: O(T × NM) — T는 치즈가 모두 녹는 시간, 매 시간마다 O(NM) DFS 수행
공간: O(NM) — 격자 배열 및 방문 배열

문제