2638, 2636 : 치즈 - JAVA

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

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

흔한 bfs문제이다.

공통으로 치즈의 구멍 부분과 치즈 바깥의 빈 공간을 구분해주어야한다. 치즈의 구멍 부분은 치즈 내부에 존재하고 치즈에 둘러싸여 있는 형태이기에 bfs 탐색을 통해 치즈가 닿으면 탐색하지 못하게 처리함과 동시에 치즈 바깥의 빈 공간은 치즈 내부의 빈 공간과 다른 숫자를 주었다.

 

그리고 치즈가 위치한 좌표를 저장해주었다.

ArrayList는 제네릭에 클래스를 집어넣을 수 있고 LinkedList에 비해 빠른 탐색 시간을 갖는다. 그래서 사용하였다.

 

저장된 치즈 좌표 하나하나 돌면서 2638번과 같은 경우 바깥면이 두개 닿은 경우를 계산하여 치즈를 삭제해주었다.

치즈가 0이 되면 치즈가 없어지기까지 얼마나 걸렸는지 출력이 된다.

 

2638번

import java.util.*;
import java.io.*;
public class Main {
	static int n, m, ccnt;
	static int[][] place;
	static boolean[][] check;
	static ArrayList<Node> cheese;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int res = 0;
		place = new int[n][m];
		cheese = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				place[i][j] = Integer.parseInt(st.nextToken());
				if(place[i][j] == 1) {
					//나중에 치즈만 방문하는 bfs 제조
					cheese.add(new Node(i,j));
					ccnt++;
				}
			}
		}
		while(ccnt!= 0) {
			res++;
			check = new boolean[n][m];
			bfs();
			melt();
		}
		System.out.println(res);
		br.close();
	}
	public static void melt() {
		for(int i = 0; i < cheese.size(); i++) {
			int cnt = 0;
			int x = cheese.get(i).x;
			int y = cheese.get(i).y;
		
			for(int j = 0; j < 4; j++) {
				int cx = x + dx[j];
				int cy = y + dy[j];
				if(place[cx][cy] == 2) {
					cnt++;
				}
 			}
			if(cnt >= 2) {
				place[x][y] = 0;
				ccnt--;
				cheese.remove(i);
				i--;
			}
		}
	}
	public static void bfs() {
		check[0][0] = true;
		place[0][0] = 2;
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0, 0));
		while(!q.isEmpty()) {
			Node nd = q.poll();
			for(int i = 0; i < 4; i++) {
				int fx = dx[i] + nd.x;
				int fy = dy[i] + nd.y;
				if(fx >= n || fy >= m || fx < 0 || fy < 0) continue;
				if(check[fx][fy] || place[fx][fy] == 1) continue;
				//외부
				place[fx][fy] = 2;
				q.add(new Node(fx, fy));
				check[fx][fy] = true;
			}
		}
	}
	static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}

 

 

2636번과 같은 경우, 치즈의 좌표를 저장하는것과 바깥면, 안쪽 공백을 비교해주는것은 동등하다. 하지만 바깥면과 닿은것이 있다면 무조건 치즈를 제거해줘야하고, 치즈가 없어지는 시간과 치즈가 완전히 없어지기 하루 전 치즈가 몇개남았는지 출력을 해줘야한다.

나는 Map을 통해 시간마다 남은 치즈수를 저장해두었고, 치즈가 완전히 없어지기 전의 값 - 1을 주어 저장된 치즈의 값을 출력을 했다.

 

2636번

import java.util.*;
import java.io.*;
public class Main {
	static ArrayList<Node> cheese;
	static int n, m, ch=0, res;
	static int[][] place;
	static boolean[][] check;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		place = new int[n][m];
		cheese = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				place[i][j] = Integer.parseInt(st.nextToken());
				if(place[i][j] == 1) {
					cheese.add(new Node(i,j));
					ch++;
				}
			}
		}
		HashMap<Integer, Integer> hm = new HashMap<>();
		while(ch != 0) {
			hm.put(res, ch);
			res++;
			check = new boolean[n][m];
			bfs();
			melt();
		}
		
		bw.write(String.valueOf(res)+'\n');
		bw.write(String.valueOf(hm.get(res-1)));
		bw.flush();
	}
	
	public static void bfs() {
		Queue<Node> q = new LinkedList<>();
		place[0][0] = 2;
		q.add(new Node(0, 0));
		check[0][0] = true;
		while(!q.isEmpty()) {
			Node nd = q.poll();
			for(int i = 0; i < 4; i++) {
				int cx = nd.x + dx[i];
				int cy = nd.y + dy[i];
				if(cx >= n || cy >= m || cx < 0 || cy < 0) continue;
				if(check[cx][cy] || place[cx][cy] == 1) continue;
				place[cx][cy] = 2;
				q.add(new Node(cx, cy));
				check[cx][cy] = true;
			}
		}
	}
	public static void melt() {
		for(int i = 0; i < cheese.size(); i++) {
			int x = cheese.get(i).x;
			int y = cheese.get(i).y;
			int cnt = 0;
			for(int j = 0; j < 4; j++) {
				int cx = x + dx[j];
				int cy = y + dy[j];
				if(place[cx][cy] == 2) {
					cnt++;
				}
			
			}
			if(cnt>= 1) {
				ch--;
				place[x][y] = 0;
				cheese.remove(i);
				i--;
			}
		}
	}
	public static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}