[백준(Baekjoon)] 2638. 치즈 (java)

퇴근길에 개발하기(땡진)·2021년 11월 1일

Java 백준 알고리즘 문제풀이 추천문제

알고리즘 👩🏻‍💻

목록 보기

31/53

안녕하세요. 오늘은 백준의 2638. 치즈 문제를 풀어보도록 하겠습니다.

문제 링크

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

문제 풀이

1) 구현방법

✔ 공기/ 치즈를 다른 숫자로 표시하기

외부공기를 2, 치즈로 둘러싸인 공기를 0, 이번 텀에 녹을 예정인 치즈는 3으로 표기합니다.

✔ 총 치즈 수 확인 후 치즈 count가 0이 될 때까지 반복

총 치즈수를 확인해 count변수에 저장하고, 치즈가 녹을 때마다 하나씩 차감해줍니다. 남아있는 치즈 수가 0이 되면 로직을 멈춥니다.

2) 함수 설명

✔ checkExternalAir: 외부 공기 '2'로 표시

board 격자에서 dfs를 활용하여 외부 공기를 2로 표시합니다.

✔ dfs: 녹을 수 있는 치즈 찾기

board 격자를 dfs를 수행하며 돌고, 녹을 수 있는 치즈를 찾아줍니다. 만약 치즈가 녹을 수 있다면 치즈를 3으로 표시해줍니다.

✔ isMelt: 녹아도 되는 치즈인지 확인

치즈 좌표 상하좌우에 있는 외부공기(2로 표시됨)의 수를 확인합니다. 만약 외부공기 수가 2 이상이면 true를 반환하고, 그 외에는 false를 반환합니다.

전체코드

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

public class Main {
    static int n, m, count, answer;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        count = 0;
        answer = 0;

        board = new int[n][m];
        visited = new boolean[n][m];

        // 치즈 1, 바깥 공기 2, 내부 공기 0
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int value = Integer.parseInt(st.nextToken());
                board[i][j] = value;

                if (value == 1) count++;
            }
        }

        while (count != 0) {
            checkExternalAir(0, 0);
            visited = new boolean[n][m];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board[i][j] == 1 && !visited[i][j]) dfs(i, j);
                }
            }

            visited = new boolean[n][m];

            //3으로 녹은 치즈를 2로 바꿔준다
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    board[i][j] = board[i][j] == 3 ? 2 : board[i][j];
                }
            }

            answer++;
        }

        System.out.println(answer);
    }

    //외부와 접촉한 공기 '2'로 표시
    static void checkExternalAir(int x, int y) {
        visited[x][y] = true;
        board[x][y] = 2;

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

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] || board[nx][ny] == 1) continue;

            board[nx][ny] = 2;
            checkExternalAir(nx, ny);
        }
    }

    //녹을 수 있는 치즈를 찾는 과정
    static void dfs(int x, int y) {
        visited[x][y] = true;

        //치즈가 녹을 수 있는 치즈인지 확인한다
        if (board[x][y] == 1 && isMelt(x, y)) {
            --count;
            board[x][y] = 3; // 녹은 치즈는 3으로 바꿔준다 (0으로 바꾸면 언제 녹았는지 구분 불가)
        }

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

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] || board[nx][ny] == 0) continue;

            dfs(nx, ny);
        }
    }

    //board[x][y]인 치즈가 녹아도 되는 치즈인지를 확인하는 과정
    //true: 녹아도 됨, false: 녹으면 안됨
    static boolean isMelt(int x, int y) {
        int air = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (board[nx][ny] == 2) ++air;
        }

        return air >= 2;
    }
}

느낀점

1) 틀린 이유

✔ melt 로직을 생각하지 못함

isMelt함수에서 외부공기를 체크하는 로직을 제대로 구현하지 못했다. 치즈가 있는 좌표(x,y)의 상하좌우만 체크하면 되는 거였는데 너무 어렵게 생각했던 것 같다.

✔ dfs/bfs 소스를 제대로 짜지 못함

문제를 풀면서 dfs/bfs 연습이 아직 많이 부족하다고 느껴졌다. 특히 dfs로직을 짤 때 내가 원하는 바를 제대로 표현할 수 없었고, 다양한 문제를 풀면서 더 연습해야겠다는 생각이 들었다.

✔ count변수와 visited배열의 부재

visited배열로 탐색여부를 체크하기만 하면 되는 문제였는데 visited배열을 사용하지 않아도 될 것이라고 판단했고 이 때문에 dfs함수를 제대로 짜지 못했다.
또한 main함수에서 while문을 사용해야 한다는 점은 알았지만, while을 언제/어떻게 끝내야 할지를 몰랐다.