[BFS] - G3_2638_치즈

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

2638번: 치즈

 

🌿 - 문제 설명

 

 

간단하게 정리하면 외부 공기랑 접촉한 치즈들 중 C로 표시된 치즈를 녹이고 전부 다 녹는데 걸리는 시간을 구하는 문제이다.

토마토 문제랑 유사해서 토마토 문제들을 풀어보고 이 문제를 풀어보면 조금 더 쉽게 풀 수 있다는 생각이 든다.

 

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

7569번: 토마토

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

7576번: 토마토

 

📌- 풀이

 

 

처음 문제를 보고 토마토 문제랑 유사하다고 생각했고 비슷하게 풀면 되겠다고 생각해서 bfs로 똑같이 풀려고 했다.

문제를 자세히 보니 치즈 문제는 외부와 내부의 공기에 따라 녹는 치즈들이 다르기 때문에 토마토와는 다르게 내,외부 공기에 대해서 신경을 써줘야 된다는 점이 다른 것 같다.

 

이 문제를 풀기 위해서는 BFS로 풀면서 아이디어를 조금 생각해내야 하는 것 같다.

 

1. 내부, 외부 공기를 따로 구별할 수 있게 만든다.

2. 외부 공기와 접촉한 면이 2면 이상인 치즈들은 녹는다.

 

이 2가지 조건을 가지고 BFS를 만들게 되면 풀리는 것 같다.

 

 

2차원 배열로 치즈의 상태를 나타내는 배열을 하나 만들고 녹일 수 있는 외부 공기에 대한 배열을 총 2가지를 만든다.

 

 

그리고 for문을 돌면서 치즈의 전체 크기를 체크하고, 치즈 상태를 입력한다.

        for(int i = 0 ;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                int n = Integer.parseInt(st.nextToken());
                if(n == 1){
                    chz++;
                }
                list[i][j] = n;
            }
        }

 

 

 

meltCheck 함수를 만들어서 현재 외부 공기에 대한 상태를 meltMap에 입력해준다.

이 작업이 끝나면 외부 공기는 1이 되고 이 외부 공기를 통해 녹일 수 있는 치즈를 확인하게 된다.

 static void meltCheck(){

        boolean[][] visited = new boolean[N][M];
        Queue<Air> que = new LinkedList<>();
        que.add(new Air(0,0));

        visited[0][0] = true;
        meltMap[0][0] = 1;
        while(!que.isEmpty()){
            Air air = que.poll();

            for(int i=0;i<4;i++){
                int nx = air.x + dx[i];
                int ny = air.y + dy[i];
                if(0<=nx && nx<N && 0<=ny && ny<M && !visited[nx][ny] && list[nx][ny] ==0){
                    visited[nx][ny] = true;
                    meltMap[nx][ny] = 1;
                    que.add(new Air(nx,ny));
                }
            }
        }

    }

 

 

치즈를 녹이는 melting함수를 만든다.

치즈의 주변 공기가 2개이상 외부 공기면 해당 치즈를 녹이고 전체 치즈 크기를 줄인다.

 static void melting(int x, int y){

        int count =0;
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(meltMap[nx][ny] == 1){
                 count++;
                 if(count >= 2){
                     chz--;
                     list[x][y] = 0;
                     break;
                 }
            }

        }
    }

 

 

위에서 만든 함수를 가지고 외부 공기에 대한 상태를 업데이트하고 외부 공기를 바탕으로 치즈를 녹이는 작업을 반복하면 치즈를 녹이는데 걸리는 시간이 출력된다.

     while(chz > 0) {

            meltCheck();
            result++;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (list[i][j] == 1) {
                        melting(i,j);
                    }
                }
            }
        }

 

 

 

🔥 - Java 전체 코드

 

package BFS.G3_2638_치즈;

import java.io.*;
import java.util.*;

public class Main {
        public static int N,M,chz=0, result =0;
        static int[][] list, meltMap;

        static int[] dx = {0,0,1,-1};
        static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();



        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new int[N][M];
        meltMap = new int[N][M];

        for(int i = 0 ;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                int n = Integer.parseInt(st.nextToken());
                if(n == 1){
                    chz++;
                }
                list[i][j] = n;
            }
        }

        while(chz > 0) {

            meltCheck();
            result++;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (list[i][j] == 1) {
                        melting(i,j);
                    }
                }
            }
        }

        System.out.println(result);

    }

    static void meltCheck(){

        boolean[][] visited = new boolean[N][M];
        Queue<Air> que = new LinkedList<>();
        que.add(new Air(0,0));

        visited[0][0] = true;
        meltMap[0][0] = 1;
        while(!que.isEmpty()){
            Air air = que.poll();

            for(int i=0;i<4;i++){
                int nx = air.x + dx[i];
                int ny = air.y + dy[i];
                if(0<=nx && nx<N && 0<=ny && ny<M && !visited[nx][ny] && list[nx][ny] ==0){
                    visited[nx][ny] = true;
                    meltMap[nx][ny] = 1;
                    que.add(new Air(nx,ny));
                }
            }
        }

    }

    static void melting(int x, int y){

        int count =0;
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(meltMap[nx][ny] == 1){
                 count++;
                 if(count >= 2){
                     chz--;
                     list[x][y] = 0;
                     break;
                 }
            }

        }
    }

}

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