[BOJ 2636] 치즈 (Java, BFS)

 

---

문제 링크 

 

풀이

- 앞서 풀었던 치즈(2638)에서 조건에 맞게 수정하여 풀었으나 마지막 98%에서  '실패했습니다' 확인 

 

https://dev-ljw1126.tistory.com/243

[BOJ 2638] 치즈 (Java, BFS)

 

 

- 마찬가지로 공기(0)인 부분에 대해 탐색을 진행하는데, 공기와 접촉한 치즈의 경우 임의 값(2)로 갱신 후 치즈 개수를 카운팅 수행 

- while 반복문 시작 하기전 녹아 없어질 치즈 처리(0)해주고, 남은 치즈(1) 여부를 파악

- 치즈가 없다면 이전 반복문 수행시 구한 TIME, COUNT 값을 그대로 출력하면 됨

- 시간 복잡도 : O(N^2)

 

그래프 탐색에서 녹을 예정인 치즈를 임의 표시한 후 while 반복문 조건에서 치즈를 녹이고, 남은 치즈를 확인하다니..
머리를 좀 굴리자 오레, 보쿠, 와타시 :(

 

참고

https://steady-coding.tistory.com/173

[BOJ] 백준 2636번 : 치즈 (JAVA)

 

---

제출 코드

BFS 의 경우

import java.util.*;
import java.io.*;

public class Main {
    
   static StringBuilder sb = new StringBuilder();

    static int R, C, TIME, COUNT;

    static int[][] FIELD;

    static boolean[][] VISIT;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        VISIT = new boolean[R][C];
        FIELD = new int[R][C];
        for(int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < C; j++) {
                int value = Integer.parseInt(st.nextToken());
                FIELD[i][j] = value;
            }
        }

        br.close();
    }

    static void bfs(int startX, int startY) {
        Queue<Integer> que = new LinkedList<>();
        que.add(startX);
        que.add(startY);
        VISIT[startX][startY] = true;

        while(!que.isEmpty()) {
            int x = que.poll(), y = que.poll();

            for(int i = 0; i < 4; i++) {
                int nx = x + DIRECTION[i][0];
                int ny = y + DIRECTION[i][1];

                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if(VISIT[nx][ny]) continue;

                if(FIELD[nx][ny] == 1) {
                    FIELD[nx][ny] = 2;
                    COUNT += 1;
                } else if(FIELD[nx][ny] == 0){
                    que.add(nx);
                    que.add(ny);
                    VISIT[nx][ny] = true;
                }
            }
        }
    }

    static boolean existCheese() {
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(FIELD[i][j] == 2) {
                    FIELD[i][j] = 0;
                }
            }
        }

        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(FIELD[i][j] == 1) {
                    return true;
                }
            }
        }

        return false;
    }

    static void initVisit() {
        if(VISIT == null) {
            VISIT = new boolean[R][C];
        } else {
            for(int i = 0; i < R; i++) {
                for(int j = 0; j < C; j++) {
                    VISIT[i][j] = false;
                }
            }
        }
    }

    static void pro() {
        while(existCheese()) {
            COUNT = 0;
            TIME += 1;
            initVisit();

            bfs(0, 0);
        }

        sb.append(TIME).append("\n").append(COUNT);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}