[BOJ 2638] 치즈 (Java, BFS)

 

---

문제 링크

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

2638번: 치즈

---

풀이

- 첫 줄 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100) 주어짐

- 치즈 (1), 없는 부분 (0)으로 표시 

- 치즈가 모두 녹아 없어지는데 필요한 시간을 출력

- 상,하,좌,우 격자형 그래프 문제 

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

 

절차*

- 가장 가리(1,1) 위치 부터 시작하여 공기(0)에 대해 BFS 탐색 수행하면 치즈를 만나면 +1 해주기 (공기와 접촉면 파악 위해)

- 탐색이 완료된 경우 적어도 2변이상 공기과 접촉한 치즈를 찾아 녹여주기(melt())

- 플래그 값 통해 치즈가 남아 있는 경우 반복, 아닌 경우 종료

 

 

공기(0)와 접촉하는 치즈(1)의 값을 갱신 후 녹인다

 

실수* 

'모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다' 를 제대로 안 읽고 문제 풀이하는 바람에 시간 소요

---

제출 코드

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

public class Main {
    
    static int N, M;

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

       N = Integer.parseInt(st.nextToken());
       M = Integer.parseInt(st.nextToken());

       FIELD = new int[N + 1][M + 1];
       for(int i = 1; i <= N; i++){
           st = new StringTokenizer(br.readLine());
           for(int j = 1; j <= M; j++) {
               FIELD[i][j] = Integer.parseInt(st.nextToken());
           }
       }
   }

   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 < 1 || ny < 1 || nx > N || ny > M) continue;
               if(VISIT[nx][ny]) continue;

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

   static boolean melt() {
       boolean result = true;
       for(int i = 1; i <= N; i++){
           for(int j = 1; j <= M; j++) {
                if(FIELD[i][j] >= 3) {
                    FIELD[i][j] = 0;
                    result = false;
                } else if(FIELD[i][j] == 2) {
                    FIELD[i][j] = 1;
                    result = false;
                }
           }
       }

       return result;
   }

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

   static void pro() {
        int timing = 0;
        while(true) {
            initVisit();

            bfs(1, 1);

            if(melt()) break;
            else timing += 1;
        }

       System.out.println(timing);
   }

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