치즈(BJ_G4_2636)

1. 문제 링크

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

2636번: 치즈

---

 

2. 나의 코드

메모리: 16000kb
시간: 160ms
코드 길이: 2639B
시간 복잡도 : O(RC)
설명
- 치즈를 녹이는 과정은 BFS를 통해 바깥쪽 치즈를 0으로 변경
- 치즈의 갯수를 세기 위해서는 완전탐색

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

public class BJ_2636 {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int R, C, result, hour;
    static int[][] map;
    static boolean[][] visited;
    static List<Point> removeList;

    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());
            }
        }
        result = cheeseCount();
        while (true) {
            int cnt = 0;
            melt();
            ++hour;
            cnt = cheeseCount();
            if (cnt == 0) {
                break;
            } else {
                result = cnt;
            }
        }
        System.out.println(hour);
        System.out.println(result);
    }

    // 치즈 녹이기
    public static void melt() {
        removeList = new ArrayList<>();
        visited = new boolean[R][C];
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(0, 0));
        visited[0][0] = true;

        while (!q.isEmpty()) {
            Point now = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = now.x + dr[d];
                int nc = now.y + dc[d];

                if (!isValid(nr, nc)) continue;
                if (visited[nr][nc]) continue;

                if (map[nr][nc] == 0) {
                    q.offer((new Point(nr, nc)));
                    visited[nr][nc] = true;
                } else if (map[nr][nc] == 1) {
                    removeList.add(new Point(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }

        for (Point p : removeList) {
            map[p.x][p.y] = 0;
        }
    }

    // 치즈 갯수 세기
    public static int cheeseCount() {
        int result = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 1) ++result;
            }
        }
        return result;
    }

    // 맵 밖으로 나가는지 검사
    public static boolean isValid(int r, int c) {
        return 0 <= r && r < R && 0 <= c && c < C;
    }
}

 

---

 

3. 정답 코드

import java.util.*;
 
public class Main {
    
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int[][] board;
    static int n, m;
    static int cheese;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        board = new int[n][m];
        cheese = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
                if(board[i][j] == 1) cheese++;
            }
        }
        
        int cheeseCount = 0;
        int time = 0;
        while(cheese != 0) {
            cheeseCount = cheese;
            time++;
            visited = new boolean[n][m];
            bfs();
        }
        System.out.println(time);
        System.out.println(cheeseCount);
    }
    
    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {0, 0});
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            int[] current = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    if(board[nx][ny] == 0) {
                        q.offer(new int[] {nx, ny});
                    } else {
                        cheese--;
                        board[nx][ny] = 0;
                    }
                }
            }
        }
    }
}

 

---

 

4. 배운 점

- 치즈의 갯수를 세는 과정에서 불필요하게 매 시간마다 치즈의 갯수를 세었다. 다른 코드를 보니 가장 처음에 치즈의 갯수를 구한 뒤 제거한 치즈 갯수를 빼기만 하면 매 시간마다 치즈의 갯수를 구하지 않아도 된다는 것을 알았다.