BOJ 2638 : 치즈 - https://www.acmicpc.net/problem/2638
외부 공기와 내부 공기를 어떻게 판단해야 할 지 고민을 많이 했던 문제다. 외부공기는 (0,0)위치부터 BFS
로 탐색하면 구할 수 있다. 스터디원들이랑 얘기해보니 DFS로도 가능한 것 같다.
치즈가 한시간 뒤 녹을 건지는 상하좌우를 확인하여 외부 공기와 두개 면 이상 맞닿아있을 경우 녹을 치즈로 판단했다.
-1
)를 판단한다.0
)으로 값을 바꾼다.구현에서 까다로웠던 점이 이미 외부 공기가 -1로 값이 들어가 있는 상태에서, 녹은 치즈를 바탕으로 다시 외부공기를 찾아줘야 한다는 점이었다. 초기 외부공기 판단 시 BFS 조건으로 상하좌우 값을 보며 옆 칸의 공기가 0
이면 큐에 넣어주면서 탐색했는데, 다음 턴에 이미 -1로 값이 들어가 있기 때문에 BFS 탐색 조건에 맞지 않았다. 이에 대한 해결로는 visited[][]를 따로 선언해서 방문하지 않았고
&& 옆 칸이 1이 아닌경우(==치즈가 아닌경우)
큐에 넣는 조건으로 해결하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int[][] map;
static boolean[][] visited;
static int n;
static int m;
static int[] mi = {0, 0, 1, -1};
static int[] mj = {1, -1, 0, 0};
static ArrayList<Loc> cheese_melt;
static class Loc{
int i;
int j;
public Loc(int i, int j) {
this.i = i;
this.j = j;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
n = Integer.parseInt(inputs[0]);
m = Integer.parseInt(inputs[1]);
map = new int[n][m];
for (int i = 0; i < n; i++) {
inputs = br.readLine().split(" ");
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(inputs[j]);
}
}
int time = 0;
cheese_melt = new ArrayList<>();
while(true){
cheese_melt.clear();
visited = new boolean[n][m];
setExternalAir(); // -1은 외부 공기, 0은 내부 공기
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
if(map[i][j]==1){ // 치즈이면
if (isMelt(i,j)) { // 1시간 내에 녹을 치즈면 == 두 변이 외부 공기와 맞닿아있으면
cheese_melt.add(new Loc(i, j));
}
}
}
}
// 더 이상 녹을 치즈가 없다 == 치즈가 다 녹았다 -> 종료!
if(cheese_melt.size()==0) break;
// 겉 치즈 녹음
for (Loc l : cheese_melt) {
map[l.i][l.j] = 0;
}
time ++;
}
System.out.println(time);
}
public static boolean isMelt(int i, int j){
int cnt = 0;
for (int d = 0; d < 4; d++) { // 상하좌우 확인
int ni = i + mi[d];
int nj = j + mj[d];
if(ni<0 || nj<0 || ni>n || nj>m) continue;
if(map[ni][nj] == -1) cnt++;
}
// 두 면 이상 맞닿아있는지 true/false로 return
return cnt >= 2;
}
public static void setExternalAir(){
Queue<Loc> q = new LinkedList<>();
q.add(new Loc(0, 0));
map[0][0] = -1;
while (!q.isEmpty()) {
Loc now = q.poll();
for (int d = 0; d < 4; d++) {
int ni = now.i + mi[d];
int nj = now.j + mj[d];
if(ni<0 || nj<0 || ni>=n || nj>=m ) continue;
if(visited[ni][nj] || map[ni][nj] == 1) continue;
visited[ni][nj] = true;
map[ni][nj] = -1; // 외부 공기는 -1로 초기화
q.add(new Loc(ni, nj));
}
}
}
}
✔ 알고리즘 분류 - 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 시뮬레이션
✔ 난이도 - 🟡 Gold 4
https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%80-2638-%EC%B9%98%EC%A6%88-java (visit 배열만 참고!)