백준 2636 치즈

백준 2636 치즈

백준 2636 치즈

구현 전 생각

먼저 4방향 탐색을 하여서 벽이거나 공백인 경우 해당 치즈를 계속 증가시켜오던 카운트 값으로 갱신한다 그리고 그 안에 치즈를 탐색하는 경우 사방탐색한 값이 1보다 큰값이면 해당 치즈를 현재 카운트 값으로 마스킹한다 그리고 배열에 카운트 값을 인덱스로 배열을 생성한뒤 현재 남아 있는 치즈의 갯수를 저장하고 마지막에 치즈가 다 사라진 뒤 해당 인덱스의 값을 넣어서 걸린 시간과 사라지기 이전의 치즈 값을 출력한다.

2.둘러 쌓여 있다는 생각을 어떻게 구현 할 수 있을까.
dfs탐색이라는 힌트를 얻어서 진행

아쉬운점

첫번째 방법은 공기가 존재하면 모두 탐색한 경우로 밀봉된 경우를 알아차리지 못했다
이렇게 막힌것을 확인하는 방법으로 DFS < BFS를 이용해서 해당 경계선에 들어간 경우 해야할 작업을 하고 continue를 이용해서 경계선을 알아 낼 수 있다.

코드 (실패한 코드)

package com.study37;

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

public class backjoon_2636_치즈 {
	static int[][] map;
	static int N,M;
	static int time=3;
	static int[] D; //인덱스를 time으로 가지고 현재 전체 치즈의 개수
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	public static void air() {
		int cnt=0;
		 //1을 2로 마스킹 하기위해서 1시간 지난 시간이 time 2에 해당한다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j]==1) {
					for (int j2 = 0; j2 < 4; j2++) {
						int nx=i+dx[j2];
						int ny=i+dx[j2];
						
						if(map[nx][ny]==0||map[nx][ny]==time-1) {
							map[i][j]=time;
							cnt++;
							break;
						}
						
						
					}
					
				}
			}
		}
		D[time++]=D[time-2]-cnt; //time-1 시간 뒤에 존재할 치즈 개수 
		
	}
	public static void main(String[] args) throws IOException {
		int end=0;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		M = Integer.parseInt(st.nextToken());
		D= new int[52];
		int totalCheese=0;
		map = new int[N][M];
		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) {
					totalCheese++;
				}
			}
		}
		D[0]=totalCheese;
		D[1]=totalCheese;
		D[2]=totalCheese;
		D[3]=totalCheese;
		
		for (int i = 3; i <=52; i++) {
			
			air();
			if(D[i]==0) {
				end = i;
				break;
			}
				
		}
		System.out.println(end-2);
		System.out.println(D[end-1]);
		
	}
}

코드(pass)

package com.study38;

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

public class backjoon_2636_치즈 {
	static int[][] map;
	static int N,M;
	static int time=0;
	static int[] D; //인덱스를 time으로 가지고 현재 전체 치즈의 개수
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static boolean[][] isSelected;
	static int total;

	static class point{
		int x,y;

		public point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
	}
	public static void air() {
		isSelected = new boolean[N][M];
		
		Queue<point> que = new LinkedList<>();
		
		que.add(new point(0,0));
		
		isSelected[0][0]=true;
		
		while(!que.isEmpty()) {
			point temp = que.poll();
			
			int x = temp.x;
			int y = temp.y;
			
			for (int i = 0; i < 4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				
				if(nx<0||ny<0||nx>=N||ny>=M) continue;
				
				if(map[nx][ny]==1) {
					
					isSelected[nx][ny]=true;
					map[nx][ny]=0;
					total--;
					continue;
				}
				
				if(isSelected[nx][ny]) continue;
				
				que.add(new point(nx,ny));
				
				isSelected[nx][ny]=true;
				
			}
		}
		
	}
	public static int clear() {
		int cnt=0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j]==-1) {
					total--;
					cnt++;
				}
			}
		}
		return cnt;
	}
	public static void main(String[] args) throws IOException {
		int end=0;
		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 totalCheese=0;
		map = new int[N][M];
		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) {
					totalCheese++;
				}
			}
		}
		total=totalCheese;
		int last=totalCheese;
		while(total>0) {
			air();
			//int temp = clear();
			time++;
			if(total>0) {
				last =total;
			}
			
		}
		System.out.println(time);
		System.out.println(last);
		
	}
}