Java 2636 치즈

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

2636번: 치즈

---

문제를 보고 치즈를 중심으로 공기와 닿는 지 아닌지를 체크하며 풀이를 하다가 문제에 가장자리에는 치즈가 놓일 수 없다는 조건을 다시 확인하였고 가장자리에서부터 녹는 치즈인지 아닌지를 체크하며 문제를 풀이하였다.

 

핵심 로직은 다음과 같다.

 

1. 초기 치즈 갯수를 카운트 해준 뒤 가장자리에서부터 상하좌우 bfs 탐색을 진행한다.

2. 치즈를 만난다면 해당 치즈는 녹는 치즈이므로 치즈 갯수를 빼준다.

3. 모든 치즈가 녹았다면 체크해둔 치즈 갯수와 진행한 횟수를 출력해준다.

 

 

---

 

 

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

public class Main {
    static int r, c;
    static int[][] map;
    static boolean[][] visited;
    static int cheese;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new int[r][c];

        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    cheese++;
                }
            }
        }

        int remain = 0;
        int time = 0;

        while(cheese != 0){
            remain = cheese;
            time++;
            visited = new boolean[r][c];
            bfs();
        }

        System.out.println(time);
        System.out.println(remain);
    }

    static void bfs(){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        visited[0][0] = true;

        while(!q.isEmpty()){
            int[] poll = q.poll();

            for(int i = 0; i < 4; i++){
                int nx = poll[0] + dx[i];
                int ny = poll[1] + dy[i];

                if(nx >= 0 && ny >= 0 && nx < r && ny < c && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    if(map[nx][ny] == 0){
                        q.offer(new int[]{nx,ny});
                    }else {
                        cheese--;
                        map[nx][ny] = 0;
                    }
                }
            }
        }
    }
}