[백준 JAVA]2636 치즈

문제

---

2636번: 치즈 (acmicpc.net)

2636번: 치즈

 

 

풀이방법

---

우선 처음 생각했던 방법은 치즈입장에서(숫자가 1이라면) 1이아닌곳을 bfs를 돌리면서 숫자가 가장자리에 도달한다면 map을 0으로 바꿔주는 방법을 생각했다. 그렇게 푸니 답은 나오지만 메모리 초과가 떠서 조금 더 효율적으로 풀 수 있는 방법을 고민했다.

 

두번째로 생각해낸 방법은 굳이 치즈입장에서 생각하지말고, 가장자리에서 치즈쪽으로 bfs를 돌리다가 치즈가 나오면 map을 0으로 바꿔주는 방법을 생각했다. 근데 다시 생각해보니 굳이 그럴 필요가 없었다.

 

최종적으로 풀이를 한 3번째 방법은, 0,0에서부터 bfs를 돌려서 1이 나오면 map2를 3으로 만드는 방법을 사용했다. 4방 탐색을 진행하면서 치즈를 만나면 map2를 3으로 바꿔준다. 값이 0이고, 방문하지 않았다면 방문처리를 해주면서 계속 큐에 넣어준다.

코드

---

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

class Cheeselist{
	int x;
	int y;
	public Cheeselist(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

public class Main_2636_이서정2{
	
	static int[][] del = {{-1,0},{1,0},{0,-1},{0,1}};
	static int map[][];
	static int map2[][];
	static int N,M;
	static boolean visit[][];
	static int count=0;
	static int countone;
	static Queue<Cheeselist> queue;
	static int cheesecount;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		map=new int[N][M];
		map2=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) {
					cheesecount++; //cheese가 없어질때까지 bfs를 돌리기 위해 초기에 cheese개수 세어주기
				}
			}
		}
		visit=new boolean[N][M];

		
		int temp=0;
		while(true) {
			visit=new boolean[N][M];
			temp=cheesecount; //while문 나가기 전 치즈개수 세어주기
			bfs(0,0); //bfs시작
			meltingcheese(); //map2의 값을 사용해서 map에 덮어씌워주기
			countone=cheesecount;
			count++; //치즈 녹이는 시간 세어주기
			if(cheesecount<=0) {
				break; //치즈의 개수가 없어지면 while문 나가기
			}
		}
		System.out.println(count);
		System.out.println(temp);
		

	}
	static void bfs(int x,int y) {
		queue = new LinkedList<>();
		queue.offer(new Cheeselist(x,y));
		
		while(!queue.isEmpty()) {
			Cheeselist c=queue.poll();
			
			for(int i=0; i<4; i++) { //4방 탐색을 진행하면서
				int nx=c.x + del[i][0];
				int ny=c.y + del[i][1];
				
				if(nx>=0 && nx<N && ny>=0 && ny<M && map[nx][ny]==1) {
					map2[nx][ny]=3; //치즈를 만나면 map2를 3으로 바꿔주기
				}
				
				if(nx>=0 && nx<N && ny>=0 && ny<M && map[nx][ny]==0 && visit[nx][ny]==false) {
					queue.offer(new Cheeselist(nx,ny)); //0이고, 방문하지 않았다면
					visit[nx][ny]=true;//방문처리해주면서 계속 큐에 넣어주기
				}
			}
			
			
		}
		
		
	}
	static void meltingcheese() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map2[i][j]==3) {
					cheesecount--;
					map[i][j]=0;
					map2[i][j]=0;
				}
				
			}
		}
	}//map2의 값을 map에 넣어주기


}