백준 2636 치즈 (자바)

<문제>

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

2636번: 치즈

 

<풀이>

위 문제에서는 외부 공기와 접촉된 치즈를 고르는 기능, 고른 치즈를 삭제하는 기능 이 2가지 기능을 구현하면 쉽게 해결하는 문제이다.

 

뒤에 2가지 기능은 비교적 단순하지만 앞에 기능이 생각하기 어려울 수 있다.

문제에서 예시로 보여주는 원래 치즈 모양이다. 여기서 외부 공기와 접촉된 부분과 내부 치즈에 둘러싸인 부분을 구분해야 한다.

해당 부분을 구분하기 위해 탐색을 이용한다. 나는 bfs로 구현했다.

외부 공기 (0,0)부터 시작해서(문제에서 판의 가장자리는 치즈가 놓여 저 있지 않다고 했다) 공기를 탐색하다가 만나는 치즈를 표시하면 된다. 이렇게 되면 치즈에 둘러싸여 있는 부분은 체크를 하지 못하기 때문에 외부 공기와 접촉된 치즈만 체크를 할 수 있다.

그 후 체크된 치즈를 공기로 바꿔주고 이 작업을 치즈가 없어질 때까지 반복하면 된다.

직전 치즈의 개수를 출력하는 부분에 대해서는 처음 치즈의 개수를 저장하고 만약 한 번에 없어질 경우 저장한 처음 치즈 개수를 출력하고,  한 번에 안 없어질 경우 치즈의 개수를 리스트에 저장하고 마지막 리스트에 저장되어 있는 치즈의 개수를 출력하면 된다.

 

위 문제같은경우 판 가장자리가 모두 공기인 것을 잘 활용해야 한다. 해당 부분을 제대로 파악하지 못해서 이중 for문에 bfs를 넣었는데 그렇게 풀었을 경우 비효율적이 되어버린다.

 

<코드>

import java.util.*;
import java.io.*;
public class Main {

    public static int n;
    public static int m;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static int resultHour = 0;
    public static ArrayList<Integer> resultCheeseCounts = new ArrayList<>();

    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());

        map = new int[n][m];
        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());
            }
        }
        int firstCheeseCount = countCheese();
        while(true) {
            resultHour++;
            visited = new boolean[n][m];
            bfs(0,0);
            int cnt = countCheese();
            if (cnt == 0) {
                break;
            }
            else {
                resultCheeseCounts.add(cnt);
            }
            removeCheese();
        }
        System.out.println(resultHour);
        if (resultCheeseCounts.size() > 0)
            System.out.println(resultCheeseCounts.get(resultCheeseCounts.size() - 1));
        else System.out.println(firstCheeseCount);


    }

    public static void bfs(int x, int y) { // 외부 공기 접촉
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x,y});

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY = now[1];

            for(int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) continue;
                if(!visited[nextX][nextY] && map[nextX][nextY] == 0) {
                    visited[nextX][nextY] = true;
                    queue.add(new int[] {nextX, nextY});
                }
                if(map[nextX][nextY] == 1 && !visited[nextX][nextY]) {// 외부 공기와 접촉하는 치즈 발견
                    visited[nextX][nextY] = true;
                    map[nextX][nextY] = -1;
                }
            }
        }
    }

    public static void removeCheese() { // 외부 공기와 접촉된 치즈를 제거하는 기능

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == -1) {
                    map[i][j] = 0;
                }
            }
        }

    }
    public static int countCheese() { // 치즈 개수 구하는 기능
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++)
                if(map[i][j] == 1) count++;
        }
        return count;
    }
}