김무성

김무성

2020.11.18 ~

[백준] 2638. 치즈

4 분 소요

문제 링크

[백준] 2638. 치즈


풀이 과정

BFS 탐색을 이용한 시뮬레이션 문제입니다.


while (!empty()) {
    time++;
    findExternalAir();
    findMeltingPos();
    melt();
}

위 과정은 모든 치즈가 녹아 없어질 때까지 아래 문제의 조건 내용을 반복합니다.

  • empty() : 모눈 종이 위에 모든 치즈가 녹아 있으면 true를, 하나라도 남아있다면 false를 리턴한다.
  • time : 현재 시뮬레이션 단계에서의 시간 초를 의미한다.
  • findExternalAir() : 치즈 내부 공기를 제외하고 외부 공기만을 찾는다.
  • findMeltingPos() : 외부 공기와 접촉되는 치즈를 찾는다.
  • melt() : findMeltingPos() 로 찾은 외부 공기와 접촉된 치즈들을 없앤다.


static boolean empty() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] != -1) return false;
        }
    }

    return true;
}

empty()는 모눈 종이 위에 모든 치즈가 녹아 있으면 true를, 하나라도 남아있다면 false를 리턴합니다.

map[i][j]가 -1이면, 공기를 의미합니다. 따라서, 모든 요소를 돌며 map[i][j] != -1 이면 치즈가 존재한다는 것을 의미하므로 즉시 false를 리턴하며, 모든 요소를 순회함에도 리턴되지 않았다면 모눈 종이에 치즈는 존재하지 않는다는 것을 의미하므로 true를 리턴합니다.


static void findExternalAir() {
    int[][] tmpMap = cloneArr();
    Queue<int[]> queue = new LinkedList<>();
    boolean[][] visit = new boolean[N + 1][M + 1];
    visit[0][0] = true;
    queue.add(new int[]{0, 0});

    while (!queue.isEmpty()) {
        int[] now = queue.poll();
        int x = now[0], y = now[1];
        tmpMap[x][y] = -1;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];

            if (!isRange(nx, ny)) continue;
            if (!(tmpMap[nx][ny] == 0 || tmpMap[nx][ny] == -1)) continue;
            if (visit[nx][ny]) continue;

            visit[nx][ny] = true;
            queue.add(new int[]{nx, ny});
        }
    }

    map = tmpMap;
}

findExternalAir()는 치즈 내부 공기를 제외하고 외부 공기만을 찾습니다.


외부 공기를 내부 공기와 분리하기 위해 배열 크기를 1씩 증가시킨 N+1, M+1로 선언해, 모눈종이의 바깥 테두리를 사용합니다.

예를 들어, 위와 같이 모눈종이의 크기가 8x9로 주어진다면, 2차원 배열을 9x10 크기로 선언해, 좌측과 우측 사이드를 외부 공기로 설정해둔 뒤 (0, 0)부터 BFS 탐색을 시작해 외부 공기를 모두 찾아냅니다.

초기 문제에서 공기는 외부, 내부 불문하고 0으로 주어집니다. 외부 공기임을 구분 짓기 위해 발견 즉시 -1로 바꿔줍니다.


static void findMeltingPos() {
    boolean[][] visit = new boolean[N + 1][M + 1];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 1 && !visit[i][j]) {
                Queue<int[]> queue = new LinkedList<>();
                visit[i][j] = true;
                queue.add(new int[]{i, j});

                while (!queue.isEmpty()) {
                    int[] now = queue.poll();
                    int x = now[0], y = now[1];
                    int cnt = 0;

                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];

                        if (!isRange(nx, ny)) continue;

                        if (map[nx][ny] == -1) {
                            cnt++;
                        }

                        if (!visit[nx][ny] && map[nx][ny] == 1) {
                            visit[nx][ny] = true;
                            queue.add(new int[]{nx, ny});
                        }

                        if (cnt >= 2) {
                            melting.add(new int[]{x, y});
                        }
                    }
                }
            }
        }
    }
}

findMeltingPos()는외부 공기와 접촉되는 치즈를 찾습니다. 동작 과정은 아래와 같습니다.

  1. 맵을 돌며 방문한 적 없는 치즈(1)를 찾는다.
  2. 1에서 구한 좌표를 시작으로 BFS 탐색을 실행한다.
  3. 치즈의 두 면 이상이 외부 공기와 접촉됐는 지를 확인하고, 그렇다면 melting 이름의 리스트에 해당 좌표를 담아둔다.


static void melt() {
    for (int[] pos : melting) {
        int x = pos[0], y = pos[1];
        map[x][y] = -1;
    }

    melting.clear();
}

melt()은 findMeltingPos()로 찾은 외부 공기와 접촉된 치즈들을 없앱니다. 리스트 melting에 담겨있는 좌표들을 하나씩 꺼내 맵에 -1로 표시해 공기로 치환합니다.


코드

import java.util.*;

public class Main {
    static int N, M;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static List<int[]> melting = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        int time = 0;

        while (!empty()) {
            time++;
            findExternalAir();
            findMeltingPos();
            melt();
        }

        System.out.println(time);
    }

    static boolean empty() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] != -1) return false;
            }
        }

        return true;
    }

    static void findExternalAir() {
        int[][] tmpMap = cloneArr();
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visit = new boolean[N + 1][M + 1];
        visit[0][0] = true;
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int x = now[0], y = now[1];
            tmpMap[x][y] = -1;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];

                if (!isRange(nx, ny)) continue;
                if (!(tmpMap[nx][ny] == 0 || tmpMap[nx][ny] == -1)) continue;
                if (visit[nx][ny]) continue;

                visit[nx][ny] = true;
                queue.add(new int[]{nx, ny});
            }
        }

        map = tmpMap;
    }

    static void findMeltingPos() {
        boolean[][] visit = new boolean[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 1 && !visit[i][j]) {
                    Queue<int[]> queue = new LinkedList<>();
                    visit[i][j] = true;
                    queue.add(new int[]{i, j});

                    while (!queue.isEmpty()) {
                        int[] now = queue.poll();
                        int x = now[0], y = now[1];
                        int cnt = 0;

                        for (int d = 0; d < 4; d++) {
                            int nx = x + dx[d], ny = y + dy[d];

                            if (!isRange(nx, ny)) continue;

                            if (map[nx][ny] == -1) {
                                cnt++;
                            }

                            if (!visit[nx][ny] && map[nx][ny] == 1) {
                                visit[nx][ny] = true;
                                queue.add(new int[]{nx, ny});
                            }

                            if (cnt >= 2) {
                                melting.add(new int[]{x, y});
                            }
                        }
                    }
                }
            }
        }
    }

    static void melt() {
        for (int[] pos : melting) {
            int x = pos[0], y = pos[1];
            map[x][y] = -1;
        }

        melting.clear();
    }

    static int[][] cloneArr() {
        int[][] tmpMap = new int[N + 1][M + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                tmpMap[i][j] = map[i][j];
            }
        }

        return tmpMap;
    }

    static boolean isRange(int x, int y) {
        return x >= 0 && x <= N && y >= 0 && y <= M;
    }
}

카테고리:

업데이트:

댓글남기기

참고