G2638. 치즈

문제

제출 코드

• 사용 알고리즘 : DFS

• 1차 시도 때, 제출 시 스택 오버플로 발생으로 실패
  • DFS부분에서 재귀를 빠져나오지 못하고 무한 루프를 도는 듯 했다
  • 내부 체크 시, 처음에 탐색하는 중심부에서 다음으로 넘어갈 때, 넘어온 칸에서는 이전 칸을 제외하고 나머지 칸에 대해 탐색하는 식으로 작성해서, 칸끼리 계속 돌고 돌았을 것으로 추정
  • 알고리즘 로직에 문제가 있는 듯 하여 다른 방법을 찾았다

• 2차시도 : 매 회차마다 외부를 탐색하는 방식으로 변경
  • 생각해보니 외곽은 항상 외부라고 정해져 있어 시작점을 잡기도 좋고 dfs한번만에 모든 외부를 탐색할 수 있어, 내부보다 외부 탐색이 더욱 적절했음을 알게됨
  • 매 회차마다 외부를 표시하는 기호를 바꿔가며 외부 마킹

package gold;

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

public class G2638_cheese {

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

	// 해당 칸(외부칸)과 연결된 모든 외부 칸을 탐색. c : 해당 회차에 탐색한 외부를 표시할 기호
	static void checkOutside(int i, int j, char c) {
		for(int d=0; d<4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];

			if(ni<0 || ni>=N || nj<0 || nj>=M || map[ni][nj]=='1' || map[ni][nj]==c) continue;
			map[ni][nj] = c;
			checkOutside(ni, nj, c);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] line = br.readLine().split(" ");
		N = Integer.parseInt(line[0]);
		M = Integer.parseInt(line[1]);

		map = new char[N][M];
		int cheese = 0;
		for(int n=0; n<N; n++) {
			map[n] = br.readLine().replace(" ", "").toCharArray();
			for(int m=0;m<M; m++) if(map[n][m] == '1') cheese++;
		}

		char outside = 'A';
		checkOutside(0, 0, outside);

		int result = 0;
		while(cheese > 0) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(map[i][j] == '1') {
						int cnt = 0;
						for(int d=0; d<4; d++) {
							if(map[i+di[d]][j+dj[d]] == outside) cnt++;
						}
						if(cnt >= 2) {
							map[i][j] = '-';
							cheese--;
						}
					}
				}
			}
			result++; outside++;
			checkOutside(0, 0, outside);
		}
		System.out.println(result);
	}

}