[BOJ - JAVA] 2638 - 치즈 (BFS, 구현)

# 주소

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

2638번: 치즈

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, t;
    static int[][] arr;
    static boolean[][] visit3;
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, 1, -1, 0};
    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());
        arr = new int[n][m];
        t = 0;
        for(int i = 0; i < n; i++){
            String str[] = br.readLine().split(" ");
            for(int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        visit3 = new boolean[n][m];
        bfs();
        System.out.println(t);
    }
    public static void bfs(){
        int zero = 0;
        while(n * m != zero) {
            zero = 0;
            emptyPossibility();
            cheeze();
            t++;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(arr[i][j] == 3)
                        arr[i][j] = 5;
                    if(arr[i][j] == 1)
                        continue;
                    if(arr[i][j] == 5 || arr[i][j] == 0){
                        zero++;
                    }
                }
            }
        }
    }
    public static void range(int x, int y){
        int z = 0;
        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(arr[nx][ny] == 5)
                z++;
        }
        if(z >= 2)
            arr[x][y] = 3;
    }
    public static void cheeze(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] == 1){
                    range(i,j);
                }
            }
        }
    }
    public static void emptyPossibility(){
        visit3 = new boolean[n][m];
        Queue<Point> empty = new LinkedList<>();
        empty.offer(new Point(0,0));
        while (!empty.isEmpty()) {
            Point now = empty.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx >= n || ny >= m || nx < 0 || ny < 0)
                    continue;
                if(visit3[nx][ny])
                    continue;
                if(arr[nx][ny] == 0 || arr[nx][ny] == 5){
                    visit3[nx][ny] = true;
                    arr[nx][ny] = 5;
                    empty.offer(new Point(nx, ny));
                }
            }
        }
    }
}
class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

푸는데 3시간 정도 걸렸던 문제입니다.

문제에 나와 있는 예제로는 충분히 예제가 통과되는데, 한 번 외부 공기와 접촉한 뒤 이어서 외부 공기와 또 접촉할 때 바뀌는 arr에 대해 체크못한 점이 시간초과가 나서 잘못 짰단 것을 깨달았습니다.

차근차근 보겠습니다.

(다른분 포스팅 1도 안본 오로지 저의 100% 코딩입니다. 물론 봐도 참고만 할 뿐이지만..)

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
t = 0;
for(int i = 0; i < n; i++){
    String str[] = br.readLine().split(" ");
    for(int j = 0; j < m; j++){
        arr[i][j] = Integer.parseInt(str[j]);
    }
}
visit3 = new boolean[n][m];
bfs();
System.out.println(t);

일단 BufferedReader로 풀었습니다.

처음엔 Scanner로 제출했는데 메모리 초과가 떠서 빠르게 풀고자 버퍼를 썼습니다.

그런데 버퍼를 쓰고 처음에 제출하니 시간초과가 뜨더라고요.

시간초과가 뜬다는 말은 N값이 매우 크거나 반복문을 통과못하고 있기 때문인데, 이 문제의 n값은 100이 Max이기 때문에 while문을 통과 못하고 있다고 생각했습니다.

일단 이 부분은 나중에 짚어보고 풀어봅시다.

 

n과 m을 StringTokenizer로 받아옵니다.

arr의 크기는 n행 m열의 크기이고 이중 for문으로 0인 곳은 공기, 1은 치즈값으로 받아옵니다.

그리고 bfs()문을 실행합니다.

이 bfs문의 안을 봅시다.

public static void bfs(){
    int zero = 0;
    while(n * m != zero) {
        zero = 0;
        emptyPossibility();
        cheeze();
        t++;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] == 3)
                    arr[i][j] = 5;
                if(arr[i][j] == 1)
                    continue;
                if(arr[i][j] == 5 || arr[i][j] == 0){
                    zero++;
                }
            }
        }
    }
}

거두절미하고 while문 내부에 있는 emptyPossibility()와 cheeze()함수를 제가 만들었는데, 이 함수를 매끄럽게 만들었어야 하는데 그러지 못해서 while문이 무한루프가 되어 시간초과가 났었습니다.

emptyPossibility()함수는 공기와 접촉해 있는 외부 공기 값을 의미합니다.

그러니까, 이 문제를 이해하려면 내부의 공기와 외부의 공기의 의미에 대해 짚을 필요가 있습니다.

외부의 공기는 외부와 이어져 있기 때문에 접촉한 부분이 2면 이상이면 한 시간 뒤 치즈가 상합니다.

하지만 내부의 공기는 제 아무리 많이 접촉해 있어도 외부와 접촉되어 있지 않으면 상하지 않는다가 키포인트입니다.

따라서 emptyPossibility()함수로 시간이 흐를 때마다 외부와 접촉하고 있는지의 여부를 판단해야합니다.

그러므로 emptyPossibility()함수를 살펴보면

public static void emptyPossibility(){
    visit3 = new boolean[n][m];
    Queue<Point> empty = new LinkedList<>();
    empty.offer(new Point(0,0));
    while (!empty.isEmpty()) {
        Point now = empty.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if(nx >= n || ny >= m || nx < 0 || ny < 0)
                continue;
            if(visit3[nx][ny])
                continue;
            if(arr[nx][ny] == 0 || arr[nx][ny] == 5){
                visit3[nx][ny] = true;
                arr[nx][ny] = 5;
                empty.offer(new Point(nx, ny));
            }
        }
    }
}

이렇게 구성했습니다.

이 함수는 여타 다른 bfs문과 별 차이는 없습니다.

empty라는 Queue에 0,0부터 넣어서 for문을 이용하여 인접해있는 부분을 계속 연결시키면 됩니다.

하지만 주의해야할 점이, 처음엔 arr값을 0으로 받아오기 때문에 0인 값만 인접해 받아도 되지만

두 번째 emptyPossibility()함수를 실행할 땐 외부의 공기는 5로 치환되어 있기 때문에 5인 값들도 모두 arr에 담아서 arr값을 5로 통일시켜주어야 한다는 점입니다.

그리고 이 함수가 종료되면 외부의 공기와 접촉해 있는 공간은 모두 5로 치환되어 있습니다.

이후 cheeze()함수가 실행됩니다.

public static void cheeze(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(arr[i][j] == 1){
                range(i,j);
            }
        }
    }
}

cheeze()함수는 이렇게 생겼습니다.

이중 for문을 이용해서 표현했는데, 만약 arr값이 1이라면 range함수를 실행시키도록 했습니다.

즉, 치즈값들은 모두 range함수를 실행할 것입니다.

그런데 우리가 체크해야할 것은 이 치즈가 2면 이상 외부의 공기와 접촉해있는지를 체크해야합니다.

따라서 range함수르 체크를 할 것인데, range함수는

public static void range(int x, int y){
    int z = 0;
    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(arr[nx][ny] == 5)
            z++;
    }
    if(z >= 2)
        arr[x][y] = 3;
}

이렇게 생겼습니다.

여기서 z는 arr에서 상,하,좌,우로 1만큼씩 이동한 값이 외부의 공기와 접촉하는 경우가 2 이상이면 z값으 하나씩 늘립니다.

그런데 이 z값이 2이상이면 한 시간 뒤에 부패해서 없어질 치즈이므로 arr값을 3으로 바꿉니다.

이런식으로 외부와 접촉할 때마다 치즈를 하나씩 없애는 것이 목표입니다.

그럼 이 모든걸 1회씩 실행한 다음인 bfs구문 내부를 살펴봅시다.

public static void bfs(){
    int zero = 0;
    while(n * m != zero) {
        zero = 0;
        emptyPossibility();
        cheeze();
        t++;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] == 3)
                    arr[i][j] = 5;
                if(arr[i][j] == 1)
                    continue;
                if(arr[i][j] == 5 || arr[i][j] == 0){
                    zero++;
                }
            }
        }
    }
}

zero를 가져오는데 이 zero가 n * m이 되면 while문을 종료시킬 것입니다.

그러니까, arr배열 내에 1이 남아 있으면 안되게끔(arr가 5 또는 0이게끔 -> 0인 이유는 딱히 5가 될 필요 없었던 내부 공기) 코드를 짜줍니다.

emptyPossibility함수와 cheeze함수가 종료된 후 시간을 의미하는 변수인 t값을 1씩 증가시킵니다.

그리고 이중for문을 이용하여 만약 arr값이 3이었던 부분은 모두 공기로 변하므로 5로 바꾸고 arr가 1인 부분이 하나라도 있다면 그냥 continue시켜버립니다.

그럼 언젠가 시간이 흐른 뒤 모든 치즈가 부패해서 없어져서 공기가 되버리면 arr값에 1이 없을테고 5또는 0인 부분들을 모두 zero에 담아서 더해주면 arr의 전체 크기인 n * m이 될 것입니다.

최종적으로 System.out.println에 t를 담아서 출력하면 정답이 됩니다.

 

번외) System.out.println(4)라고 써놓고 왜 다른 예제의 답이 2초인데 4초가 나오지 하며 한참 고민했던 시간도 있었습니다. 바보같지만 진짜입니다. t위에 4가 있는 것도 아닌데 저렇게 써놓고 계속 몰라본 것도 신기하네요 ㅋㅋㅋ