백준 2636번 : 치즈 풀이(Java)

www.acmicpc.net/problem/2636

2636번: 치즈

바로 AC가 나와서 기분이 좋았다 ㅎ

BFS 로 풀 수 있는 문제이다.

Key Point

1. 현재 치즈들의 위치를 arraylist에 담아주고, 모든 치즈들에 대해 영역 바깥으로 갈 수 있는지를 체크해준다. 만약 bfs 로 탐색하면서, 이미 방문한 곳이거나, 그 위치에 치즈가 있다면 그 지점은 바깥에 닿지 않는, 즉 그 시간 대에서는 공기 중으로 사라지지 않는 안전한 치즈이다.

2. 중요 : 치즈들을 돌면서 map의 바깥에 갈 수 있다면, 즉 사라져야 하는 치즈라고 바로 삭제시켜서는 안된다. 바로 삭제시켜버리면 그 치즈에 의해 보호받던 안쪽의 치즈들까지 원치 않게 사라져버릴 것이기 때문이다. 나의 경우는 삭제시켜야 하는 치즈들과 그렇지 않은 치즈들의 ArrayList를 만들어서, 그렇지 않은 치즈들, 즉 생존한 치즈들이 남지 않을 때 까지 while 문으로 돌려주었다.

3. 내가 실수했던 부분인데, 

11111

11011

11111

이 있다면, 중간의 0과 맞닿는 부분들이 삭제 되어서는 안된다. 1번과 같은 맥락이다. 내부의 공기는 아무 상관 없으므로, 반드시 bfs 를 돌면서 map 의 바깥으로 갈 수 있는 것들이 삭제되어야 한다.

 

위의 두 가지를 감안하면 쉬운 문제이다. 골드 치고 굉장히 빨리 푼 것 같다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int R,C;
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Node> cheeses;

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


    static void input() throws IOException {
        StringTokenizer rc = new StringTokenizer(bufferedReader.readLine());
        R = Integer.parseInt(rc.nextToken());
        C = Integer.parseInt(rc.nextToken());
        map = new int[R][C];
        cheeses = new ArrayList<>();
        for(int i = 0; i < R; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) {
                    cheeses.add(new Node(i, j));
                }
            }
        }
    }

    static boolean bfs(Node start, boolean[][] visited) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);
        while(!queue.isEmpty()) {
            Node s = queue.poll();
            int x = s.x;
            int y = s.y;
            visited[x][y] = true;
            for(int i = 0 ; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >= R || ny >= C) {
                    return true;
                }
                if(visited[nx][ny] || map[nx][ny] >= 1) continue;
                queue.add(new Node(nx, ny));
                visited[nx][ny] = true;
            }
        }
        return false;
    }

    static void printMap() {
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static void solve() {
        int count = 0;
        int time = 0;
        while (!cheeses.isEmpty()) {
            ArrayList<Node> newCheeses = new ArrayList<>();
            ArrayList<Node> deleteCheeses = new ArrayList<>();
            for(Node cheese : cheeses) {
                if(!bfs(cheese, new boolean[R][C])) {
                    newCheeses.add(cheese);
                } else {
                    deleteCheeses.add(cheese);
                }
            }
            for(Node cheese : deleteCheeses) {
                map[cheese.x][cheese.y] = 0;
            }
            count = cheeses.size();
            cheeses = newCheeses;
            time++;
//            printMap();
//            System.out.println("=================");
        }
        System.out.println(time);
        System.out.println(count);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
    }
}