백준 2638번 (java)

백준 2638번: 치즈 java

관찰

공기부분 4변에서 bfs를 시작하여 2번이상 접촉 된 블럭을 표시해주고 삭제해주고 모두 삭제되면 끝!

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n,m; // 가로 세로
    static int[][] map; // 원본 배열
    static int[][] visited; // 방문 배열
    static int res; // 정답 cnt
    static int rest; // 총 남은 치즈 수
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new int[n][m];
        rest = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) rest++;
            }
        }
        res = 0;
        while(true){
            // 완전히 없어졌다면 탈출
            if(rest <= 0) break;
            // 4변에서 bfs 출발
            visited = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(i == 0 || j == 0 || i == n-1 || j == m-1) {
                        if(visited[i][j] == 0) {
                            bfs(i, j);
                        }
                    }
                }
            }
            int count = 0;
            // visited 2 이상을 녹이기
            for(int i=1;i<n-1;i++){
                for(int j=1;j<m-1;j++){
                    if(map[i][j] == 1 && visited[i][j] >= 2){
                        count++;
                        map[i][j] = 0;
                    }
                }
            }

            rest -= count;
            res++;

        }

        System.out.println(res);

    }

    private static void bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c});
        visited[r][c] = 1;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cr = cur[0], cc = cur[1];
            //System.out.println("cr = " + cr + ", cc = " + cc);
            if(map[cr][cc] == 1) {
                visited[cr][cc]++;
                continue;
            }
            for(int i=0;i<4;i++){
                int nr = cr + dr[i];
                int nc = cc + dc[i];
                if(isOut(nr,nc)){ // 만약 안에서 4변으로 들어왔다면 visited
                    if(!isOut(cr,cc))visited[nr][nc] = 1;
                    continue;
                }
                if(map[nr][nc] == 1){ //치즈에 접촉했다면 visited++
                    visited[nr][nc]++;
                    continue;
                }
                if(visited[nr][nc] != 0)continue;
                visited[nr][nc] = 1;
                q.add(new int[]{nr, nc});
            }
        }
    }

    private static boolean isOut(int nr, int nc) {
        return nr<1 || nr>=n-1 || nc<1 || nc>=m-1;
    }
}

풀이

각 4변에서 모두 bfs를 돌리는 것이 아닌 한 곳에서 bfs를 돌릴 때 탐색 안해도 되는 것들을 표시해주면서 탐색한다면 시간 효율을 챙길 수 있음! 그렇게 두변 이상 접촉한 치즈를 표시하고 지워주면서 정답 갯수를 세면 풀리는 문제

느낀점

완전탐색으로 푼 것 같아서 살짝 걱정했지만 적절한 최적화가 들어가줘서 무난하게 해결된 것 같다!