🔍 문제
💻 제출
문제에 나와있는 테스트 예제만 보고 DFS로 풀이 하려고 시도 했다.
하지만 허를 찌르는 반례가 하나 있었고 DFS로는 풀이하기 어지러워서 BFS로 급하게 노선을 틀었다.
비슷한 문제가 하나 더 있었는데 그때 코드와 크게 다르지는 않다.
📌 입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
📌 출력
출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.
🤔 생각
해당 문제는 이전 치즈 문제와 다르게 공기 영역이 두번이상 닿아야 사라진다.
BFS로 탐색하면서 공기영역이 몇번 닿는지를 카운트 한다. max = 2
2번 닿으면 해당 치즈 영역을 빈 공간으로 바꿔주면 될 듯 하다.
모든 치즈가 사라질 때 까지 BFS탐색을 반복한다.
시간과 메모리 제한이 빡빡해서 최소한의 과정으로 풀어야 한다고 생각 했다.
본인은 시간제한 1초 , 메모리 제한 128MB 면 그냥 빡빡하다고 생각한다.
📝 첫번째 코드(실패, DFS 사용)
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static int cheeseCnt = 0;
static int time = 0;
static int[] dx = {0, 1, 0, -1}; //동 남 서 북
static int[] dy = {1, 0, -1, 0}; //동 남 서 북
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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++) {
StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
int data = Integer.parseInt(stD.nextToken());
if (data == 1) { //치즈 개수 계산
cheeseCnt++;
}
map[i][j] = data;
}
}
while (cheeseCnt != 0) {
//맵에 치즈가 존재 하지 않을 때 까지 반복
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
if (map[i][j] == 1){
for (int v=0; v<N; v++){
Arrays.fill(visited[v],false);
}
time++;
dfs(i,j);
}
}
}
}
bw.write(time + "\n");
bw.flush();
bw.close();
br.close();
}
static void dfs(int x,int y) {
visited[x][y] = true;
int cnt = 0;
for (int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (0<=nx && nx<N && 0<=ny && ny<M){
//영역 안에 있어야 함
if (visited[nx][ny] == false){ //다음 영역이 방문하지 않은 상태 라면
if (map[nx][ny] == 0){ //공기가 닿는 부분
cnt++;
}
else{
dfs(nx,ny);
}
}
}
}
if (cnt>=2){
map[x][y] = 0; //사라지는 치즈
cheeseCnt--;
}
}
}치즈 영역으로 부터 처음 시작해서 동 남 서 북 시계 방향으로 깊이 우선 탐색을 시작한다.
다음 영역이 공기 영역이라면 cnt를 해주기 때문에
if (visited[nx][ny] == false){ //다음 영역이 방문하지 않은 상태 라면
if (map[nx][ny] == 0){ //공기가 닿는 부분
cnt++;
}
else{
dfs(nx,ny);
}
}재귀가 끝나고 cnt가 2이상 이라면 빈 영역으로 변환 한다.
if (cnt>=2){
map[x][y] = 0; //사라지는 치즈
cheeseCnt--;
}하지만 위와 같은 코드로는 풀 수 없는 반례가 있다.
7 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 1 0 0
0 1 0 1 0 1 0
0 0 1 0 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0와 같은 반례가 주어질때 모든 1이 인접해 있지 않기 때문에 각 1은 다른 시간 대로 판단 한다. <= 허점
또한 내부 공간에 대한 고려 역시 따로 필요 하므로 정상적인 결과를 받아 낼 수 없다.
📝 두번째 코드(정상 제출, BFS 사용)
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static int cheeseCnt = 0;
static int time = 0;
static int[] dx = {0, 1, 0, -1}; //동 남 서 북
static int[] dy = {1, 0, -1, 0}; //동 남 서 북
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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++) {
StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
int data = Integer.parseInt(stD.nextToken());
if (data == 1) { //치즈 개수 계산
cheeseCnt++;
}
map[i][j] = data;
}
}
while (cheeseCnt != 0) {
//맵에 치즈가 존재 하지 않을 때 까지 반복
bfs();
time++;
}
bw.write(time + "\n");
bw.flush();
bw.close();
br.close();
}
static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0});
boolean visited[][] = new boolean[N][M];
visited[0][0] = true;
while (!q.isEmpty()) {
int[] now = q.poll();
int nowX = now[0];
int nowY = now[1];
for (int i = 0; i < 4; i++) {
int nx = nowX + dx[i];
int ny = nowY + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < M){
if (map[nx][ny] == 1 && visited[nx][ny] == true){
//현재 방문이 두번째 방문 이라면 , 공기에 두번 닿는 상태
map[nx][ny] = 0;
cheeseCnt--;
}
if (visited[nx][ny] == false){
if (map[nx][ny] == 1){
visited[nx][ny] = true; //공기에 1번 닿은 상태
}
else if (map[nx][ny] == 0){
visited[nx][ny] = true;
q.offer(new int[] {nx,ny});
}
}
}
}
}
}
}내부 공기 영역에 대한 고려가 필요없는 BFS를 통해 가장자리 부터 접근 을 시도 했다.
공기 영역은 큐에 넣어주면서 탐색을 이어가고 치즈 영역은 접근을 두가지로 분리 하여 시도 했다.
한번이라도 방문을 한다면 치즈, 공기 영역에 상관 없이 visited[index] = true; 로 변환 되기 때문에 flag의 역할이 가능하다.
if (map[nx][ny] == 1 && visited[nx][ny] == true){
//현재 방문이 두번째 방문 이라면 , 공기에 두번 닿는 상태
map[nx][ny] = 0;
cheeseCnt--;
}
이후 두번째 접근 시도가 발생한다면 해당 공간을 빈 공간으로 바꿔준다.
📗 정리
이번 문제보다 난이도가 낮은 치즈 문제를 한번 풀어 봤던 경험이 있기 때문에 금방 풀 수 있었던 것 같다.
이번 문제 역시 난이도가 높지는 않지만 한번 경험했던 유형은 체감 난이도가 급격하게 떨어지는 것 같으며 많은 문제를 접하는게 문제 풀이 속도에 큰 영향을 줄 것이라 생각 한다.
문제 자체가 재밌다고 생각이 들어서 빨리 해결 했다고도 생각 한다.
