G2636. 치즈

문제

제출 코드

• 사용 알고리즘 : DFS

• 비슷한 문제를 이전에 푼적 있다.
• 항상 배열의 가장자리는 치즈가 없는 공기부분임을 이용하여, 매 시간마다 공기부분에서 완전탐색을 돌리면 외부공간이 모두 연결되어있음을 이용해서 외부에 접촉한 치즈를 체크한다.
• visit배열을 따로 만들지 않고, 매 시간마다 탐색하는 부분을 기존 map에 해당 시간 값을 넣어 표시해줬다.

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G2636_cheese {

	static int N, M, total=0, time=0;
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	static int[][] map;

	static void dfs(int i, int j) {
		for(int d=0; d<4; d++) {
			if(total==0) return;
			int ni = i + di[d];
			int nj = j + dj[d];
			if(ni<0 || ni>=N || nj<0 | nj>=M || map[ni][nj]==time) continue;

			int nw = map[ni][nj];
			map[ni][nj]=time;
			if(nw < time) dfs(ni, nj);
			else total--;
		}
	}

	public static void main(String[] args) throws 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++) {
				if(Integer.parseInt(st.nextToken())==1) {
					map[i][j] = Integer.MAX_VALUE;
					total++;
				}else {
					map[i][j] = 0;
				}
			}
		}

		int now=0;
		while(total>0) {
			now = total;
			map[0][0] = ++time;
			dfs(0, 0);
		}
		System.out.println(time + "\n" + now);
	}
}