BOJ 2636 치즈(JAVA) 🧀

문제 링크

2636번: 치즈

문제 설명

시간마다 가장자리의 치즈를 제거하고,
모든 치즈를 제거하는 데 걸리는 시간과 마지막으로 남은 치즈를 출력하는 문제

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

구조화

가장 자리의 치즈(1)를 구하기 위해 공기(0)를 활용하여 탐색, 포인트는 0을 사용하는 것!

오답 노트

탐색을 할때 타겟값 설정을 잘하자

소스 코드

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

public class Main {

    static int R, C, cheese, melt;
    static int[][] map;
    static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    static boolean[][] visited;
    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 r = 0; r < R; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
                if (map[r][c] == 1)
                    cheese++;
            }
        }

        int time = 0;
        while (cheese!=0) {
            melt = 0;
            visited = new boolean[R][C];
            dfs(0, 0);
            cheese -= melt;
            time++;
        }
        System.out.println(time);
        System.out.println(melt);

    }

    private static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();

        q.offer(new int[] { x, y });
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + way[i][0];
                int ny = cur[1] + way[i][1];

                // 0일 때 q offer
                if (isRight(nx, ny) && !visited[nx][ny] && map[nx][ny] == 0) {
                    q.offer(new int[] { nx, ny });
                    visited[nx][ny] = true;
                }
                // 1일 때 녹은 치즈++;
                else if (isRight(nx, ny) && !visited[nx][ny] && map[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    map[nx][ny] = 0;
                    melt++;
                }
            }
        }
    }

    private static void dfs(int x, int y) {
        visited[x][y] = true;

        if(map[x][y] == 1)
        {
            melt++;
            map[x][y] = 0;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + way[i][0];
            int ny = y + way[i][1];

            // 0일 때 q offer
            if (isRight(nx, ny) && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }

    private static boolean isRight(int nx, int ny) {
        if (nx >= 0 && nx < R && ny >= 0 && ny < C)
            return true;
        return false;
    }

}

git hub 링크

 

DFS, BFS 성능 비교

	메모리	시간
dfs	15340 KB	144 ms
bfs	15936 KB	164 ms