[백준][bfs][Java] 2638. 치즈 : 골드 3

문제 링크: https://www.acmicpc.net/problem/2638

1. 문제 해석

외부 공기인지 먼저 확인 후, 치즈가 녹을 수 있는 조건인지 확인한다.

처음에는 어떻게 이 공기를 치즈안에 갇힌걸 판단할까 고민이 많았다... 관점을 치즈로 시작하면 이 공기가 외부공기인지 안에 있는 공기인지 판단할 수 없다는걸 깨달았다. 해결책이 안보일땐,, 다르게 생각해보자 !!!!!!!!

무조건 외부 공기인 좌표 (0,0)를 기준으로, 외부 공기를 체크해보자! 라는 생각에서 아래와 같은 구현이 시작되었다.

 

 3단계 흐름으로 동작한다.

1. 외부 공기 확장 (findAir)
2. 녹을 치즈 전체 탐색
3. 녹은 치즈 → 공기로 확장

이 과정을 치즈가 다 녹을 때까지 반복한다.

2. 초기 외부 공기 설정

List<Point> start = new ArrayList<>();
start.add(new Point(0,0));
findAir(start);

0,0)은 항상 외부 공기다. 이 지점에서 시작해서:

air[i][j] = true;

로 외부 공기 영역 전체를 표시한다.

 

3. 치즈 녹이기

for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] == 1 && isOutSide(i, j)) {
                        start.add(new Point(i, j));
                        cheeseCnt--;
                    }
                }
            }

배열을 돌면서, 외부 공기에 2면 이상 닿은 치즈는 녹인다.

 

4. 외부 공기 확장 함수

public static void findAir(List<Point> points)

 

 

4-1. 치즈 제거

arr[p.i][p.j] = 0;
air[p.i][p.j] = true;

녹은 치즈를 바로 공기로 바꾼다

 

4-2. 외부 공기 확장 (BFS)

air[ni][nj] = true;
q.add(new Point(ni, nj));

 

 

5. 시간 복잡도

공기 BFS 1번 + 전체 탐색 1번

한 턴 = O(N*M)

전체 = O(T * N * M)

 

6. 코드 풀이

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

public class Main{
    static int N, M;
    static boolean[][] air;
    static int[][] arr;
    static int cheeseCnt = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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());

        air = new boolean[N][M];
        arr = new int[N][M];

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

        List<Point> start = new ArrayList<>();
        start.add(new Point(0,0));
        findAir(start);

        int time = 0;

        while(true) {
            time++;
            start = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] == 1 && isOutSide(i, j)) {
                        start.add(new Point(i, j));
                        cheeseCnt--;
                    }
                }
            }

            findAir(start);

            if (cheeseCnt == 0)
                break;
        }

        System.out.print(time);
    }

    public static boolean isOutSide(int i, int j){
        int outSide = 0;

        for(int a = 0; a < 4; a++){
            int ni = i + dx[a];
            int nj = j + dy[a];

            if(ni < 0 || ni >= N || nj < 0 || nj >= M)
                continue;

            if(air[ni][nj]) outSide ++;
        }

        return outSide >= 2;
    }

    public static void findAir(List<Point> points){
        Queue<Point> q = new LinkedList<>();

        for(Point p : points){
            q.add(new Point(p.i, p.j));
            arr[p.i][p.j] = 0;
            air[p.i][p.j] = true;
        }

        while(!q.isEmpty()){
            Point cur = q.poll();

            for(int i = 0; i < 4; i++){
                int ni = cur.i + dx[i];
                int nj = cur.j + dy[i];

                if(ni >= N || ni < 0 || nj >= M || nj < 0)
                    continue;

                if(air[ni][nj] || arr[ni][nj] == 1)
                    continue;

                air[ni][nj] = true;
                q.add(new Point(ni, nj));
            }
        }
    }


    public static class Point{
        int i, j;
        public Point(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
}