[백준] 2636, 2638 치즈 (그래프 탐색/Java)

[백준] 2636 치즈

2636. 치즈 - 골드4

📌 풀이 과정

 

외부 공기 (0,0) 위치를 시작점으로 bfs 탐색을 시작한다.

현재 탐색할 대상인 위치가

 

1. 공기인 경우(0)

큐에 넣어 다음 탐색에서도 이 공기와 연결된 좌표를 계속해서 탐색해 나갈 수 있도록 한다.

 

2. 치즈인 경우(1)

탐색 중 이 좌표가 치즈라면, 외부 공기와 접촉한 것이므로 녹여야 한다.

치즈를 공기(0)로 바꾸어 녹인 뒤, 남은 치즈 개수를 감소 시킨다. cheese--

여기서 중요 포인트!!!

녹인 치즈는 큐에 넣지 않는다.
큐에 넣게 되면 새로 녹은 공기가 내부 공기와 접촉할 위험이 있기 때문에
안쪽에 있는 치즈가 의도치 않게 녹을 수 있다.

 

 

✨ 제출 코드

package beakjoon;

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

public class 치즈_2636 {
	
	static int N, M, cheese;
	static int[][] map;
	static boolean[][] visited;
	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());
		map = new int[N][M];
		visited = new boolean[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) cheese++;
			}
		}
		
		int cheeseCnt = 0; // 마지막으로 남아있던 치즈 개수
		int time = 0; // 모든 치즈가 녹을때까지 걸린 시간
		while(cheese != 0) { // 치즈가 남아있는 동안 반복
			cheeseCnt = cheese;
			time++;
			visited = new boolean[N][M];
			bfs(0, 0);
		}
		
		System.out.println(time);
		System.out.println(cheeseCnt);
	}
	
	private static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {x, y});
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			int[] tmp = q.poll();
			x = tmp[0];
			y = tmp[1];
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) continue;
				
				visited[nx][ny] = true;
				if(map[nx][ny] == 0) { // 공기인 경우 계속 탐색
					q.offer(new int[] {nx, ny});
				}
				else { // 치즈인 경우
					cheese--; // 치즈 녹이기
					map[nx][ny] = 0;
				}
			}
		}
	}
	

}

 

---

 

[백준] 2638 치즈

2638. 치즈 - 골드3

📌 풀이 과정

치즈는 외부 공기와 접촉한 경우에만 녹기 때문에, 외부 공기를 명확히 구분하는 것이 중요하다.

한 라운드에서 녹을 치즈를 모두 찾고, 한꺼번에 녹여야 한다. 그 치즈 위치를 외부 공기로 설정해야 한다.

만약 외부 공기를 판별하지 않고 치즈를 녹이게 되면

내부 공기와 외부 공기의 구분이 모호해져 의도치 않게 내부의 치즈가 빨리 녹을 수 있다.

외부 공기와 2변이 맞닿아 있다고 치즈를 바로 녹이게 되면
그 순간 외부 공기가 된 치즈가 다른 치즈와 새로운 접촉을 만들기 때문에
원래 의도와는 다르게 내부의 치즈가 더 빨리 녹아서 문제가 된다.

 

1. 외부 공기 판별하기

(0,0)에서 시작하여 BFS로 탐색하며 외부 공기를 모두 찾아 표시한다.

이때 외부 공기 좌표는 큐에 넣어 다음 탐색에 사용한다.

 

2. 녹일 치즈 후보 찾기

치즈 중에서 외부 공기와 2변 이상 접촉한 치즈를 찾아 녹일 대상으로 표시해야 한다.

이 치즈들은 바로 녹이지 않고 별도의 큐에 모아둔다.

 

3. 치즈 녹이기

녹일 대상 치즈를 한꺼번에 녹인다.

이 치즈들은 외부 공기가 되므로 외부 공기 큐에 추가하여 다음 라운드에 새로운 외부 공기로 활용한다.

→ 별도의 방문 배열을 사용할 필요가 없어짐

 

 

✨ 제출 코드

package beakjoon;

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

public class 치즈_2638 {

	static int N, M, cheese, time;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static Queue<int[]> q = new LinkedList<>();

	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());
		map = new int[N][M];
		visited = new boolean[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)
					cheese++;
			}
		}

		time = 0;
		q.add(new int[] { 0, 0 }); // 외부 공기 탐색 시작점
		visited[0][0] = true;
		
		// 치즈가 모두 녹을 때까지 반복
		while (cheese > 0) {
			findExternalAir(); // 외부 공기 탐색
			melting(); // 치즈 녹이기
			time++;
		}

		System.out.println(time);
	}

	private static void findExternalAir() {
		// BFS로 외부 공기 탐색
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int x = cur[0];
			int y = cur[1];

			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 || visited[nx][ny])
					continue;

				// 공기(0)인 경우 외부 공기로 표시하고 큐에 추가
				if (map[nx][ny] == 0) {
					map[nx][ny] = -1;
					visited[nx][ny] = true;
					q.add(new int[] { nx, ny });
				}
			}
		}
	}

	private static void melting() {
		Queue<int[]> cheeseQ = new LinkedList<>();

		// 외부 공기와 접촉한 치즈 찾기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 1 && checkAir(i, j)) { // 외부 공기와 2변 이상 접촉한 치즈
					cheeseQ.add(new int[] { i, j });
					visited[i][j] = true;
				}
			}
		}

		// 녹을 치즈들을 외부 공기로 만들고 치즈 개수 감소
		while (!cheeseQ.isEmpty()) {
			int[] cur = cheeseQ.poll();
			int x = cur[0];
			int y = cur[1];
			map[x][y] = -1;
			cheese--;
			q.add(new int[] {x, y}); // 녹은 치즈는 다음 라운드의 외부 공기로 사용
		}

	}

	// 치즈가 외부 공기와 2변 이상 접촉하는지 확인
	private static boolean checkAir(int x, int y) {
		int cnt = 0;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M)
				continue;
			if (map[nx][ny] == -1)
				cnt++;
			if (cnt == 2) // 두 면 이상 접촉 시
				return true;
		}
		return false;
	}

}