[BAEKJOON_2636 - JAVA] 치즈

문제

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

2636번: 치즈

해당글의 내부 공기는 치즈의 뚤려있는 구멍을 뜻합니다.

과정

1.  BFS를 통해 치즈내부의 공기를 제외한 외부의 공기들을 구분. 
2.  치즈와 맞닿은 외부 공기를 기준으로, 치즈를 meltQueue에 입력 후 targetCheese 호출.
3.  2번에서 입력된 치즈를 외부 공기로 치환하며, 치환된 공기를 updateAirQueue에 입력.
4.  위의 2,3번 과정을 반복하며, updateAirQueue에 값이 없을 경우 반복문 종료.
5.  외부공기를 나타내는 cnt로 횟수를 나태냈지만, 초기화를 2로 했기에
    출력할 경우 -2를 한다.

 

 

풀이

• 문제 지문을 보면, '네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며' 이 부분이 중요하다.
  치즈 둘레에 1칸이상의 공간이 있다는 얘기.
  이를 활용, BFS를 통해 치즈를 녹이는 외부 공기를 탐색.
  
• 치즈를 녹이는 외부 공기를 탐색할 때, 치즈와 맞닿은 공기를 meltQueue에 삽입.
  삽입후 공기를 기준으로 맞닿은 치즈를 다시 탐색해 공기로 치환하며 updateAirQueue에 삽입.
  
• 위의 밑줄친 두줄이 가능한것은 한번 맞닿았던 공기들은 다시 치즈에 맞닿을 일이 없기때문에 가능.
  ( -> 둘러쌓던 부분의 치즈들은 반드시 공기로 변하며, 내부의 치즈들은 새로 나타난 공기와 맞닿음.)
  이후 과정을 치즈가 사라질 때까지 반복.

 

문제해결

구현 자체는 어렵지 않았지만 메모리 초과를 해결하는데 꽤나 어려움을 겪음.
처음에는 메모리를 줄이고자 cnt를 통해 visit 관리를 해보려 시도했으나, 구현을 하면서 방향을 잃었다.
결국엔 visit 배열을 통해 중복 검사를 줄여 해결.

→ 설계의 중요성 cnt를 통해 메모리를 줄여보고자 했지만, 작성 중 방문관리를 할수 없는 요소들 존재
많은 경험을 통해 빈틈없는 설계를 하자. ( 테스트 통과 후 최적화를 하자)

 

 

알고리즘 지식

• BFS
• 구현 능력

 

 

JAVA코드

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

/*
 *  입력
 *  치즈 : 1
 *  없는 경우 : 0
 *  
 *  판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
 *  -> 내부 외부를 구분할 방법
 *  
 *  출력 
 *  첫줄 : 치즈가 녹는데 소요되는 시간. -> 시간(수행 횟수)
 *  다음줄 : 모두 녹기 한시간 전 남아있는 치즈 조각 수. -> 출력 전 조각
 *  
 *  map -> -1 : 치즈  / 0 : 내부  / cnt : 외부 공기 
 *  
 *  치즈와 맞다은 공기를 기준으로 풀이
 */

class pair {
	int row;
	int col;

	public pair(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

public class Main {

	static int N, M, last, cnt; 	// 행, 렬, 마지막 치즈 조각, 시간
	static boolean check = true; 	// while 문을 위한 boolean
	static int[][] map; 			// 입력받을 2차원 배열
	static boolean[][] visit; 		// 방문 관리 2차원 배열
	static Queue<pair> updateAirQueue = new LinkedList<pair>(); // 주변을 외부 공기로 변환 할 좌표
	static Queue<pair> meltQueue = new LinkedList<pair>(); 		// 주변 치즈를 녹일 공기 좌표

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	// 범위 검사
	public static boolean isValid(int row, int col) {
		if (row < 0 || row >= N || col < 0 || col >= M)
			return false;
		return true;
	}

	// 내부 공기 -> 외부 공기 구분 및 변환
	public static void makeMapBFS() {

		// 첫 호출만 동작
		if (updateAirQueue.isEmpty())
			updateAirQueue.offer(new pair(0, 0));

		while (!updateAirQueue.isEmpty()) {
			int row = updateAirQueue.peek().row;
			int col = updateAirQueue.poll().col;
			map[row][col] = cnt; 	// 외부공기 구분
			visit[row][col] = true;

			for (int k = 0; k < 4; k++) {
				int nextRow = row + dy[k];
				int nextCol = col + dx[k];

				// 범위 검사
				if (!isValid(nextRow, nextCol))
					continue;

				// 방문 검사
				if (visit[nextRow][nextCol])
					continue;

				// 내부 공기 외부공기로 치환
				if (map[nextRow][nextCol] == 0) {
					visit[nextRow][nextCol] = true; // 방문 처리
					updateAirQueue.offer(new pair(nextRow, nextCol));
					continue;
				}

				// 주변에 치즈가 있는 경우
				if (map[nextRow][nextCol] == -1) {
					visit[nextRow][nextCol] = true;
					meltQueue.offer(new pair(row, col)); // 주변 치즈를 녹일 공기 좌표를 큐에 삽입.
				}
			}
		}
	}

	// 치즈 녹이기 && 치즈 -> 공기로 바뀐 좌표 처리
	public static void targetCheese() {

		while (!meltQueue.isEmpty()) {
			int row = meltQueue.peek().row;
			int col = meltQueue.poll().col;

			for (int k = 0; k < 4; k++) {
				int nextRow = row + dy[k];
				int nextCol = col + dx[k];

				// 범위 검사 && 주변이 치즈인 경우
				if (isValid(nextRow, nextCol) && map[nextRow][nextCol] == -1) {
					map[nextRow][nextCol] = cnt + 1; 					// 해당 자리는 공기로 치환 (변환된 치즈의 개수)
					updateAirQueue.offer(new pair(nextRow, nextCol)); 	// 큐에 입력(이웃한값들을 탐색하기 위해)
				}
			}
		}

		// 더이상 치즈가 없는 경우
		if (updateAirQueue.isEmpty()) {
			check = false;
			return;
		}

		++cnt; // 횟수 추가
		last = updateAirQueue.size(); // 치즈 개수
	}

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];		// 입력 받을 2차원 배열
		visit = new boolean[N][M];	// 방문 관리 2차원 배열
		cnt = 2; 	// 외부 공기 및 시간 관리
		last = 0; 	// 마지막 치즈 조각 개수

		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());
				if (map[i][j] == 1) {
					map[i][j] = -1; // 치즈인 경우
				}
			}
		} // end of input


		while (check) {
			makeMapBFS(); 	// 공기 구분
			targetCheese(); // 치즈 녹이기
		}

		sb.append(cnt - 2 + "\n" + last + "\n");
		br.close();
		System.out.println(sb);
	}
}