[백준] 2636 치즈

1. 문제

www.acmicpc.net/problem/2636

2636번: 치즈

2. 접근방법

맵으로 주어진 모양에서 테두리 만 지워 나가며 

몇 시간째에 다 지워지는지 마지막엔 몇개의 치즈가 지워졌는지 구하는 문제

 

처음에 치즈의 테두리를 어떻게 구할까? 로 접근 했다가 삽질을 굉장히 오래했다..

 

그런데 생각을 바꿔 외부공기가 닿는 치즈는 사라진다로 접근하면 훨씬 쉽게 풀 수 있다.

 

0,0은 항상 공기라고 했으니 0,0부터 외부공기를 bfs로 채워넣으면서

치즈가 닿으면 치즈를 삭제하고 visit처리만 하고 que에는 안넣으면 된다.

 

그렇게 계속 반복하게 하여 풀이하였다.

 

근데 이렇게 계속 반복하면 최악 N*N*N/2 이 되는데 N이 작아서 가능하지만 더 효율적인 방법으로

이미 지나온 공기들을 또 갈 필요없이 전 시간에 삭제되었던 치즈의 위치부터 다시 돌리면

N*N으로 맵 한번만 쭉 돌려봐도 가능하다고 한다.

3. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2636치즈 {
	static int map[][], M, N, size;
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new int[M][N];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		int time = 0;
		int presize = 0;
		while (true) {
			fillair();
			if (size == 0)
				break;
			presize = size;
			time++;
		}
		System.out.println(time);
		System.out.println(presize);

	}

	static void fillair() {
		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(0, 0));
		boolean visit[][] = new boolean[M][N];
		visit[0][0] = true;
		int clonemap[][] = new int[M][N];
		size = 0;
		for (int i = 0; i < M; i++)
			clonemap[i] = map[i].clone();

		while (!que.isEmpty()) {
			Point now = que.poll();
			for (int i = 0; i < 4; i++) {
				int row = now.x + dr[i];
				int col = now.y + dc[i];
				if (row < 0 || col < 0 || row >= M || col >= N)
					continue;
				if (visit[row][col])
					continue;
				if (map[row][col] == 1) {
					visit[row][col] = true;
					clonemap[row][col] = 0;
					size++;
					continue;
				}
				visit[row][col] = true;
				que.offer(new Point(row, col));
			}
		}
		map = clonemap;
	}
}

4. 마치며

치즈의 테두리를 어떻게 구하지만 생각하다가 삽질을 너무 오래했다.

잘 안풀릴때는 역으로 생각하는 습관을 가지도록 하자.