백준 2638번: 치즈 [JAVA]

https://www.acmicpc.net/problem/2638

2638번: 치즈

 

 * 풀이

가장 바깥의 공간부터 사방을 탐색한다. 주변에 빈 공간이 있다면 다음 공간도 탐색하고 치즈를 만난다면 체크만 한다. 치즈를 두 번 만난 경우 표시를 0으로 바꿔 치즈를 없앤다. 이 반복을 치즈가 모두 사라질 때까지 반복하고 반복한 횟수를 출력한다.

 

* 코드

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

public class Main {
	static int N, M;
	static int map [][];
	static int CHEEZE;
	static int remain;
	static int cnt;
	static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,1,-1};
	static boolean isVisited[][];
	
	static boolean checkValid(int x, int y) {
		if (x<0 || x>=N || y<0 || y>=M) return false;
		else return true;
	}
	
	static void removeCheeze(int x, int y) {
		
		for (int i=0; i<4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];
			
			if (!checkValid(next_x, next_y)) continue; // 범위 밖일 경우 무시
			
			if (map[next_x][next_y]==1) { // 치즈
				if (isVisited[next_x][next_y]) {
					map[next_x][next_y] = 0; // 두 번 만난 경우 사라짐
					remain--; // 남은 치즈 - 1
				}
				else { // 처음 만난 경우
					isVisited[next_x][next_y] = true; // 방문 체크
				}
			}
			
			else { // 공기
				if (!isVisited[next_x][next_y]) { // 처음 만났다면
					isVisited[next_x][next_y] = true;
					removeCheeze(next_x, next_y); // 이동
				}
			}
			
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.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(bf.readLine());
			for (int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j]==1) CHEEZE++;
			}
		}
		
		remain = CHEEZE;
		
		while(remain!=0) {
			isVisited = new boolean [N][M];
			removeCheeze(0,0);
			cnt ++;
		}
		System.out.println(cnt);
	}

}