[백준] 치즈_2636 - 공룡 루디

 치즈 2636번 solved.ac 골드 5

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

2636번: 치즈

 문제 해석 및 풀이

 

이 문제는 공기 중에 노출된 치즈가

몇 시간 뒤에 완전히 녹는지와

완전히 녹기 직전 단계에서 몇 개의 치즈가 남았는지를 구하는 문제입니다.

 

문제의 조건에서 가장 테두리 부분은 치즈가 놓여있지 않고

공기가 있는 부분입니다.

 

이 문제에서는 시간마다 없어지는 치즈를 구해

그 치즈를 없애야 합니다.

 

이 문제를 접근하기 위해서는

공기에 노출된 치즈를 알아야 하는데

이 방법으로는 bfs, dfs 둘 다 풀 수 있습니다.

 

제가 접근한 방법은 bfs로

공기를 기준으로 상하좌우를 탐색하여

해당 칸이 공기면 다시 큐에 넣고 방문 처리하고

치르면 해당 치즈를 방문 처리하고 0으로 바꾸는 방법으로 했습니다.

 

시간마다 공기에 노출되는 치즈가 다르기 때문에

bfs탐색을 치즈가 완전히 없어질 때까지 하기 위해

각 시간마다 총치즈에서 녹는 치즈를 빼는 방법을

이용하여 해당 연산이 0이 되면

걸리는 시간과 마지막에 녹은 치즈를 출력해주면 해결되는 문제입니다.

 

큐를 하나만 써서 하는 방법 (매 시간마다 0,0부터 탐색을 시작)

package b2636_치즈;

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

public class Main {

	static int time = 0;
	static int totalCnt = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		String[] inp = br.readLine().split(" ");
		int H = Integer.parseInt(inp[0]);
		int W = Integer.parseInt(inp[1]);

		int[][] map = new int[H][W];
		
		boolean [][]visited =new boolean[H][W];
		
		int [] dr= {-1,1,0,0};
		int [] dc= {0,0,-1,1};

		for (int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < W; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					totalCnt++;
			}
		}

		ArrayDeque<int[]> q = new ArrayDeque<>();//공기를 넣는 큐

		do {
			q.add(new int[] { 0, 0 }); //0,0은
			visited[0][0]=true;
			int cnt=0;
			while (!q.isEmpty()) {
				int [] now=q.poll();
				int r=now[0];
				int c=now[1];
				
				for(int i=0;i<4;i++) {//사방탐색
					int rr=r+dr[i];
					int cc=c+dc[i];
					
					if(rr>=0&&rr<H&&cc>=0&&cc<W) {
						if(visited[rr][cc]) continue;
						if(map[rr][cc]==1) { //치즈면
							cnt++;// 카운트 증가
							visited[rr][cc]=true; //방문처리
							map[rr][cc]=0; //0으로 바꿈
						}else { //공기면
							q.add(new int[] {rr,cc});
							visited[rr][cc]=true;
						}
					}
				}
			}
			time++;
			if(totalCnt-cnt==0) {
				System.out.println(time);
				System.out.println(totalCnt);
				break;
			}else totalCnt-=cnt;
			
			for(int i=0;i<H;i++) { //방문 처리 초기화
				for(int j=0;j<W;j++)
					visited[i][j]=false;
			}
			
		} while (true);

	}
}

큐를 2개 써서 하는 방법

이 방법은 녹는 치즈의 위치부터 탐색을 시작하는 방법입니다.

이 방법을 쓰게 되면 방문처리를 초기화하는 작업을 안 해도 되고 무조건 0,0부터 탐색을 시작하는

첫 번째 방법보다 효율적입니다.

//큐를 2개 써서 하는 방법
package b2636_치즈;

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

public class Main2 {

	static int time = 0;
	static int totalCnt = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		String[] inp = br.readLine().split(" ");
		int H = Integer.parseInt(inp[0]);
		int W = Integer.parseInt(inp[1]);

		int[][] map = new int[H][W];
		
		boolean [][]visited =new boolean[H][W];
		
		int [] dr= {-1,1,0,0};
		int [] dc= {0,0,-1,1};

		for (int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < W; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					totalCnt++;
			}
		}

		ArrayDeque<int[]> q = new ArrayDeque<>();//공기를 넣는 큐
		ArrayDeque<int[]> q2 = new ArrayDeque<>();//치즈를 넣는 큐
		q.add(new int[] { 0, 0 }); //0,0은 맨 처음 한번만
		visited[0][0]=true;
		do {
			while (!q2.isEmpty()) { //녹은 치즈의 위치부터 탐색
				q.add(q2.pollFirst());
			}

			int cnt=0;
			while (!q.isEmpty()) {
				int [] now=q.poll();
				int r=now[0];
				int c=now[1];
				
				for(int i=0;i<4;i++) {//사방탐색
					int rr=r+dr[i];
					int cc=c+dc[i];
					
					if(rr>=0&&rr<H&&cc>=0&&cc<W) {
						if(visited[rr][cc]) continue;
						if(map[rr][cc]==1) { //치즈면
							cnt++;// 카운트 증가
							visited[rr][cc]=true; //방문처리
							map[rr][cc]=0; //0으로 바꿈
							q2.add(new int[] {rr,cc});
						}else { //공기면
							q.add(new int[] {rr,cc});
							visited[rr][cc]=true;
						}
					}
				}
			}
			time++;
			if(totalCnt-cnt==0) {
				System.out.println(time);
				System.out.println(totalCnt);
				break;
			}else totalCnt-=cnt;
		} while (true);

	}
}

아래 방법이 큐 하나만 사용했을 때고

위 방법이 큐 두 개를 사용했을 때입니다. 

맵이 커지면 커질 수록 큐 두 개를 사용했을 때 효과를 볼 수 있을 것 같습니다.