[백준 - Java] 2638번 : 치즈

문제

www.acmicpc.net/problem/2638

2638번: 치즈

문제 조건 

치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다.

그러므로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다.

그러나 한 시간 후, 이 공간으로 외부 공기가 유입되면 오른쪽 그림과 같이 C로 표시된 치즈 격자들이 사라지게 된다.

 

파란색으로 칠해진 부분이 외부 공기, 빨간색으로 칠해진 부분이 치즈 내부의 공기이다.

 

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 

입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

설명 

처음엔 그냥 공기에 맞닿으면 다 녹이면 되는줄 알았다ㅎㅎ 문제를 제대로 안 읽었던 것....

위의 왼쪽 그림처럼 파란색 외부 공기와 맞닿은 치즈만 녹여야 한다.

 

이를 위해서 DFS 또는 BFS로 외부 공기인지 아닌지를 판별한다.

가장자리는 무조건 공기이기 때문에 (0, 0)부터 시작한다.

치즈를 만난 경우는 패스하고, 공기를 만난 경우만 외부 공기라는 의미로 2로 바꿔준다. 

1-1. DFS로 외부 공기 판별하기

// dfs로 외부와 접촉한 공기 2로 표시
static void dfs(int x, int y) {
	visited[x][y] = true;
	map[x][y] = 2; // 외부 공기라는 의미로 2로 바꿔줌 

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

		dfs(nx, ny); // 공기인 경우만 dfs 수행 
	}
}

1-2. BFS로 외부 공기 판별하기

// bfs로 외부와 접촉한 공기 2로 표시
public static void bfs() {
	Queue<Point> queue = new LinkedList<>();
	queue.add(new Point(0, 0));
	visited[0][0] = true;
	map[0][0] = 2;

	while(!queue.isEmpty()) {
		int x = queue.peek().x;
		int y = queue.poll().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 (visited[nx][ny] || map[nx][ny] == 1) continue; 

			map[nx][ny] = 2; // 외부 공기라는 의미로 2로 바꿔줌 
			queue.add(new Point(nx, ny)); // 공기인 경우만 큐에 넣어줌
			visited[nx][ny] = true;
		}
	}
}

2. 치즈 녹이기

DFS와 BFS를 수행하고 나면 외부 공기들은 모두 2로 바뀌었다.

 

이제 melting함수에서 치즈를 녹인다.

처음 map을 입력받을 때 치즈인 경우만 모아 치즈 리스트를 만들었다.

치즈 리스트를 순회하며 2칸 이상 외부 공기와 접촉하고 있는 치즈인 경우

치즈 리스트에서도 삭제하고 map도 0으로 만들어준다.

 

static void melting() {
	for(int i = 0; i < cheeseList.size(); i++) {
		int x = cheeseList.get(i).x;
		int y = cheeseList.get(i).y;
		int cnt = 0;

		for(int j = 0; j < 4; j++) {
			int nx = x + dx[j];
			int ny = y + dy[j];

			if(map[nx][ny] == 2) 
				cnt++;
		}

		if(cnt >= 2) { // 외부 공기와 2변 이상 접촉한 경우 
			map[x][y] = 0;
			cheeseCnt--;
			cheeseList.remove(i);
			i--;
		}
	}
}

 

1번과 2번 과정을 치즈의 개수가 0이 될 때까지 반복하면 된다.

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] map;
	static boolean[][] visited;
	static ArrayList<Point> cheeseList;
	static int cheeseCnt = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		map = new int[N][M];
		cheeseList = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 1) {
					cheeseList.add(new Point(i, j));
					cheeseCnt += 1;
				}
			}
		}

		int time = 0;

		while(cheeseCnt != 0) {
			time++;
			visited = new boolean[N][M];
			dfs(0, 0); // 외부 공기 찾기 
			// bfs();
			melting(); // 치즈 녹이기 
		}

		System.out.println(time);
	}

	static void melting() {
		for(int i = 0; i < cheeseList.size(); i++) {
			int x = cheeseList.get(i).x;
			int y = cheeseList.get(i).y;
			int cnt = 0;

			for(int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];

				if(map[nx][ny] == 2) {
					cnt++;
				}
			}

			if(cnt >= 2) { // 외부 공기와 2변 이상 접촉한 경우 
				map[x][y] = 0;
				cheeseCnt--;
				cheeseList.remove(i);
				i--;
			}
		}
	}


	// dfs로 외부와 접촉한 공기 2로 표시
	static void dfs(int x, int y) {
		visited[x][y] = true;
		map[x][y] = 2; // 외부 공기라는 의미로 2로 바꿔줌 

		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 (visited[nx][ny] || map[nx][ny] == 1) continue; // 외내부 공기 판별을 위해 치즈인 경우도 pass 

			dfs(nx, ny); // 공기인 경우만 dfs 수행 
		}
	}

	// bfs로 외부와 접촉한 공기 2로 표시
	public static void bfs() {
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(0, 0));
		visited[0][0] = true;
		map[0][0] = 2;

		while(!queue.isEmpty()) {
			int x = queue.peek().x;
			int y = queue.poll().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 (visited[nx][ny] || map[nx][ny] == 1) continue; // 외내부 공기 판별을 위해 치즈인 경우도 pass 

				map[nx][ny] = 2; // 외부 공기라는 의미로 2로 바꿔줌 
				queue.add(new Point(nx, ny)); // 공기인 경우만 큐에 넣어줌
				visited[nx][ny] = true;
			}
		}
	}

}

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

GITHUB

github.com/KwonMinha/BOJ/tree/master/BOJ%232638/src

KwonMinha/BOJ