백준 2636, 2638번 치즈

 

www.acmicpc.net/problem/2636

2636번: 치즈

www.acmicpc.net/problem/2638

2638번: 치즈

너비 우선 탐색의 대표 문제 치즈입니다.

다른 분들이 푼 문제들 순서대로 정리해놓은 것들 보았을때 자주 본 기억이 있네요.

좋은 문제인듯 해요~~

 

예전에 처음 풀려고 시도했을때 분명 성공률은 높은데

도저히 생각이 안나서 포기했었던 기억이 납니다만

다시 해보니 아주 어렵지는 않은 문제였네요ㅎㅎ;

 

2636번에서 한 가지 조건이 추가된 문제가 2638번인데요.

그렇기에 2636번을 먼저 풀고 2638번을 풀었더니 수월하게 해결할 수 있었습니다.

 

구현한 부분은 다음과 같습니다.

• 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;

public class Cheeze2638 {
	int height, width, cheezeNum = 0, deleteCount, time;
	ArrayList<Point> cheezeList = new ArrayList<>();
	Queue<Point> surfaceQueue = new LinkedList<>();
	int[][] map;
	boolean[][] isNotVisted;
	boolean canDelete;
	int[] xDir = { 0, 0, -1, 1 };
	int[] yDir = { -1, 1, 0, 0 };

	public class Point {
		int x, y;

		public Point(int y, int x) {
			// TODO Auto-generated constructor stub
			this.x = x;
			this.y = y;
		}
	}

	public void bfsCheeze() {
		int i, j, x, y, queueSize;
		Point nowPoint;
		for (i = 0; i < height; i++)
			Arrays.fill(isNotVisted[i], true);

		surfaceQueue.add(new Point(0, 0));
		isNotVisted[0][0] = false;
		deleteCount = 0;
		time++;
		
		while (!surfaceQueue.isEmpty()) {
			nowPoint = surfaceQueue.remove();

			for (i = 0; i < 4; i++) {
				x = nowPoint.x + xDir[i];
				y = nowPoint.y + yDir[i];

				if (x >= 0 && x < width && y >= 0 && y < height && map[y][x] == 0 && isNotVisted[y][x]) {
					surfaceQueue.add(new Point(y, x));
					isNotVisted[y][x] = false;
				}else if (x >= 0 && x < width && y >= 0 && y < height && map[y][x] == 1 && isNotVisted[y][x]) {
					cheezeList.add(new Point(y, x));
					isNotVisted[y][x] = false;
				}
			}
		}
		
		int checkCount;
		for(Point tmp : cheezeList) {
			checkCount = 0;
			for (i = 0; i < 4; i++) {
				x = tmp.x + xDir[i];
				y = tmp.y + yDir[i];
				
				if(x >= 0 && x < width && y >= 0 && y < height && map[y][x] == 0 && !isNotVisted[y][x]) {
					checkCount++;
				}
			}
			
			if(checkCount >= 2) {
				isNotVisted[tmp.y][tmp.x] = true;
				map[tmp.y][tmp.x] = 0;
				deleteCount++;
			}
		}
		cheezeList.clear();
		
		cheezeNum -= deleteCount;
		if(cheezeNum == 0)
			canDelete = false;
	}

	public void setNum() throws IOException {
		int i, j;

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());

		map = new int[height][width];
		isNotVisted = new boolean[height][width];
		canDelete = true;
		time = 0;
		
		for (i = 0; i < height; i++) {
			st = new StringTokenizer(bf.readLine());
			for (j = 0; j < width; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					cheezeNum++;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Cheeze2638 main = new Cheeze2638();
		main.setNum();
		
		while(main.canDelete) {
			main.bfsCheeze();
		}
		System.out.println(main.time);
		//System.out.println(main.deleteCount);
	}

}

반성할 점

• 포인트 클래스 만들지 말고 쓰기!
• dir 배열로 BFS를 FOR문으로 돌리기!