b2636_치즈

 

2636번: 치즈

 

다른 분의 코드를 참고해서 BFS로 풀었는데.. BFS ㅠㅠ

BFS문제를 더 많이 풀어봐야겠다,,,,,

package w0915.b2636_치즈;

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

// BFS
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int[][] map = new int[R][C];
        int cnt = 0;
        for (int r = 0; r < R; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(st.nextToken()); //치즈가 없는 칸은 0, 치즈가 있는 칸은 1
                if(map[r][c]==1) cnt++;
            }
        }

        int circle = 0; //치즈가 모두 녹아 없어지는 데 걸리는 시간
        int solCnt = 0; //모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수

        // 우 하 좌 상
        int[] dr = {0, -1, 0, 1};
        int[] dc = {1, 0, -1, 0};

        while (cnt != 0){
            circle++;
            solCnt = cnt;

            Queue <int[]> q = new LinkedList<>();   // BFS 사용
            q.add(new int[] {0,0});     //BFS 시작

            boolean [][] visit = new boolean[R][C];
            visit[0][0] = true;         //방문 처리

            while (!q.isEmpty()){
                int [] current  = q.poll(); // r, c 가져오기

                for (int d = 0; d < 4; d++) {
                    int nr = current[0] + dr[d];
                    int nc = current[1] + dc[d];
                    if(nr<0 || nc<0 || nr>=R || nc>=C || visit[nr][nc]== true) continue;

                    if(map[nr][nc]==1){     // 치즈가 있으면
                        map[nr][nc] = 0;    // 치즈를 없애고
                        cnt--;              // 치즈의 갯수를 감소시킨다
                    }
                    else if(map[nr][nc]==0){   //치즈가 없으면
                        q.add(new int[] {nr,nc});   // 큐에 좌표를 넣어준다
                    }

                    visit[nr][nc] = true;   //방문처리
                }
            }
        }

        System.out.print( circle + " " + solCnt);

        br.close();
    }
}