/ BOJ

BOJ_2636_치즈_JAVA

문제 : 치즈

링크 : BOJ_2636_치즈

접근 방식

오랜만에 긴 호흡의 문제인 것 같다. 치즈가 있고, 한 시간에 한 번씩 표면이 녹는다. 이때, 치즈가 모두 녹을때까지의 시간과 마지막으로 모두 녹기 이전의 치즈의 면적을 구하면 되는 문제이다.

일단 딱 보자마자 BFS로 풀면 되곘다는 생각이 들었다. 그렇다면 이제 문제는 2가지이다.

  1. 치즈의 가장자리를 구분하기

  2. 치즈로 둘러쌓여있는 공간은 공기와 맞닿은 것이 아니기 때문에 녹지 않는데, 이 구간에 대한 처리

이 두 가지 문제를 해결하면 문제 해결이 가능하다.

나는 가장자리를 구하는 부분은 BFS를 치즈가 아닌 구간을 돌려서 치즈와 만나는 순간 해당 위치를 별개의 값(ex: 3)으로 바꾸어 가장자리를 표시해두고, 모든 BFS처리를 마친 후에 가장자리의 값을 한 번에 제거하는 방식을 채택했다.

또한 치즈로 둘러쌓인 공간 빈 공간을 기준으로 BFS를 돌리면서 벽과 만나지 않는 경우에 대해서 벽과 만나지 않은 빈 공간의 경우 값을 1인 그대로 두는 방식을 사용했다.

이렇게 되면 벽에 부딛힌 상태의 치즈의 겉면은 별개의 값인 3으로 표시가 되고, 녹지 않는 내부의 치즈는 변동이 없어지기 때문에, 치즈 의 겉면과 내부 공간의 구분이 가능해진다.

치즈가 모두 없어지기 전의 면적은 매 BFS 호출마다 남은 치즈의 면적을 확인해 갱신시켜 체크하면 된다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Node{

	int x;
	int y;

	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}


}
public class BOJ_2636_치즈 {

	static int N, M;
	static int[][] arr;
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	static boolean visited[][];
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int time = 0;
		int check = 0;
		while(true) {
			visited = new boolean[N][M];
			int cnt = 0;
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(arr[i][j] == 0 && visited[i][j] == false) {

						bfs(new Node(i,j),0);
					}
				}
			}
//			for(int i=0;i<N;i++) {
//				System.out.println(Arrays.toString(arr[i]));
//			}
//			System.out.println("==========================================");
			boolean endCheck = false;
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(arr[i][j] != 1 && arr[i][j] != 0) {
						arr[i][j] = 0;
						cnt++;
						endCheck = true;
					}
				}
			}
//			for(int i=0;i<N;i++) {
//				System.out.println(Arrays.toString(arr[i]));
//			}
			if(!endCheck) {
				System.out.println(time);
				System.out.println(check);
				return;
			}
			time++;
			check = cnt;			

		}


	}

	public static int bfs(Node node, int cnt) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(node);
		visited[node.x][node.y] = true;
		boolean innerCheck = false;
		ArrayList<Node> nodes = new ArrayList<>();
		while(!queue.isEmpty()) {
			Node temp = queue.poll();
			for(int d=0;d<4;d++) {
				int dx = temp.x + dir[d][0];
				int dy = temp.y + dir[d][1];
				if(dx >= 0 && dx < N && dy >= 0 && dy < M) {
					if(arr[dx][dy] != 0) {
						nodes.add(new Node(dx,dy));
						if(arr[dx][dy] != 3) {
							arr[dx][dy] = 1;
						}
						cnt++;
					}else if(visited[dx][dy] != true){
						visited[dx][dy] = true;
						queue.offer(new Node(dx,dy));
					}
				}else {
					innerCheck = true;
					continue;
				}

			}
		}
		if(innerCheck) {
			for(int i=0,n=nodes.size();i<n;i++) {
				int x = nodes.get(i).x;
				int y =nodes.get(i).y;
				arr[x][y] = 3;
			}
			return cnt;
		}else {
			return 0;
		}

	}



}

풀이 방법

  1. line 9 ~ 20 : BFS 탐색을 할 때 사용할 좌표값을 가지고 있는 객체를 생성할 클래스. 멤버변수로 좌표값을 가지고 있다.

  2. line 23 ~ 26 : 멤버 변수 선언부

  3. line 26 ~ 42 : 멤버 변수 할당(input)

  4. line 45 ~ 81 : 남은 치즈가 없을 때까지 반복하는 반복문

  5. line 48 ~ 55 : 이차원 배열을 탐색하여 탐색하지 않은 상태의 공기가 있다면 bfs를 돌힌다.

  6. line 60 ~ 69 : bfs를 마치고 치즈의 겉면으로 표시되어있는 부분을 제거하는 구문, 제거할 치즈가 없다면 마지막이므로 반복문을 나가기 위해 boolean 변수의 값을 true로 바꿔준다.

  7. line 73 ~ 77 : 더이상 치즈가 없을 때 지난 시간과 마지막으로 남은 치즈의 면적을 출력하고 return;

  8. line 78 ~ 79 : 반복 전에 시간을 1 증가시키고 마지막으로 수행한 반복의 남은 치즈의 면적을 갱신한다.