[BOJ/Java] 치즈 (2638)

치즈 (2638)

1. 문제 분석

문제 개요

• N x M 크기의 종이에서 치즈가 놓여있으며, 치즈는 1로 표시된다. 치즈의 가장자리는 공기와 접촉할 때 녹게 되며, 두 면 이상이 공기와 접촉한 치즈는 한 번의 과정에서 모두 녹는다. 치즈가 모두 녹을 때까지의 시간을 계산하는 문제이다.

입력 형식

• 첫 줄에는 종이의 크기 N (세로)과 M (가로)가 주어진다.
• 그다음 N개의 줄에 걸쳐서 각 칸에 치즈가 있는지 없는지에 대한 정보가 주어진다. 0은 공기, 1은 치즈를 나타낸다.

출력 형식

• 치즈가 모두 녹는 데 걸리는 시간을 출력한다.

2. 알고리즘 종류

• 이 문제는 DFS(깊이 우선 탐색)와 시뮬레이션을 사용하는 문제이다. DFS를 사용해 치즈의 외부 공기를 탐색하고, 시뮬레이션을 통해 치즈가 녹는 과정을 반복적으로 수행해 해결한다.

3. 주요 부분 및 코드 작성 방법

1. DFS 사용

• DFS를 통해 치즈의 외부 공기를 탐색하고, 내부 공기를 확인하여 치즈가 두 면 이상 공기와 접촉했는지 판단한다.

2. 치즈 녹이기 시뮬레이션

• 치즈가 녹는 과정을 반복하여 모든 치즈가 녹을 때까지 시뮬레이션을 수행한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
    StringTokenizer st = new StringTokenizer(br.readLine()); // 한 줄의 입력을 공백을 기준으로 나누어 처리
  
    N = Integer.parseInt(st.nextToken()); // 종이의 세로 크기 입력
    M = Integer.parseInt(st.nextToken()); // 종이의 가로 크기 입력
  
    paper = new int[N][M]; // 종이의 크기만큼 2차원 배열 초기화

  • BufferedReader와 StringTokenizer를 사용해 입력을 처리한다.

• 종이 상태 초기화 및 입력된 위치 저장

    for(int i = 0; i < N; i++) {
        st = new StringTokenizer(br.readLine()); // 한 줄의 입력을 공백을 기준으로 나누어 처리
        for(int j = 0; j < M; j++) {
            paper[i][j] = Integer.parseInt(st.nextToken()); // 치즈 및 공기 정보를 2차원 배열에 저장
        }
    }

  • 입력받은 치즈와 공기 정보를 2차원 배열 paper에 저장한다.

• 치즈 녹이기 시뮬레이션 및 결과 출력

    boolean flag = true; // 치즈가 모두 녹았는지 여부를 확인하는 변수
    int cnt = 0; // 치즈가 녹는 데 걸리는 시간을 저장하는 변수
  
    while (flag) {
        checked = new boolean[N][M]; // 내부 공간 확인을 위한 boolean 배열 초기화
        dfs(0, 0); // 치즈의 외부 공간을 파악하기 위한 DFS 수행
  
        for(int i = 0; i < N; i++) { // 모든 위치를 순회하며
            for(int j = 0; j < M; j++) {
                if(paper[i][j] == 1) counting(i, j); // 치즈가 있는 위치에서 공기와의 접촉 면 수를 계산
            }
        }
  
        int cheese = 0; // 녹은 치즈의 개수를 저장하는 변수
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(paper[i][j] > 1) { // 두 면 이상 공기와 접촉한 치즈라면
                    paper[i][j] = 0; // 해당 치즈를 녹임
                    cheese++; // 녹은 치즈 개수 증가
                }
            }
        }
  
        if(cheese == 0) { // 녹을 치즈가 더 이상 없다면 시뮬레이션 종료
            flag = false;
            break;
        }
  
        cnt++; // 치즈가 모두 녹지 않았다면 시간을 증가시키고 다음 반복 수행
    }
    System.out.println(cnt); // 최종 결과 출력

  • while 루프를 통해 치즈가 모두 녹을 때까지 반복적으로 DFS와 시뮬레이션을 수행하며, 최종적으로 치즈가 모두 녹는 데 걸리는 시간을 출력한다.

(2) 공기와 접촉한 치즈 판단 함수 (counting)

• 공기 접촉 면 계산

    int cnt = 0; // 공기와 접촉한 면의 수를 저장하는 변수
  
    for (int i = 0; i < 4; i++) { // 4방향으로 탐색 (상하좌우)
        int nr = r + dr[i]; // 새로운 행 위치
        int nc = c + dc[i]; // 새로운 열 위치
  
        if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue; // 지도를 벗어난 경우 건너뜀
        if(paper[nr][nc] == 0 && checked[nr][nc]) cnt++; // 공기와 접촉한 면이라면 cnt 증가
    }
  
    if(cnt >= 2) paper[r][c] = cnt; // 두 면 이상이 공기와 접촉한 경우 해당 위치를 녹일 준비

  • 치즈가 공기와 접촉한 면의 수를 계산하여, 두 면 이상이 공기와 접촉한 경우 녹도록 설정한다.

(3) 치즈 외부 공간 파악 함수 (dfs)

• DFS를 통한 외부 공기 탐색

    checked[r][c] = true; // 현재 위치를 방문 처리
  
    for (int i = 0; i < 4; i++) { // 4방향으로 탐색 (상하좌우)
        int nr = r + dr[i]; // 새로운 행 위치
        int nc = c + dc[i]; // 새로운 열 위치
  
        if(nr < 0 || nc < 0 || nr >= N || nc >= M || checked[nr][nc]) continue; // 지도를 벗어나거나 이미 방문한 경우 건너뜀
        if(paper[nr][nc] == 0) { // 외부 공기라면
            dfs(nr, nc); // 재귀 호출을 통해 탐색 계속
            checked[nr][nc] = true; // 탐색 완료 후 방문 처리
        }
    }

  • 현재 위치에서 4방향으로 인접한 칸들을 탐색하며, 범위 내에 있고 방문하지 않았으며 외부 공기라면 DFS를 재귀 호출해 탐색을 이어간다.

5. 전체 코드

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

public class BOJ2638 {
    static int N, M;
    static int[][] paper;
    static boolean[][] checked; // 치즈 내부 공간 체크
    static int[] dr = {-1, 1, 0, 0}; // 방향 배열: 상하좌우
    static int[] dc = {0, 0, -1, 1}; // 방향 배열: 상하좌우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringTokenizer st = new StringTokenizer(br.readLine()); // 한 줄의 입력을 공백을 기준으로 나누어 처리

        N = Integer.parseInt(st.nextToken()); // 종이의 세로 크기 입력
        M = Integer.parseInt(st.nextToken()); // 종이의 가로 크기 입력

        paper = new int[N][M]; // 종이의 크기만큼 2차원 배열 초기화

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine()); // 한 줄의 입력을 공백을 기준으로 나누어 처리
            for(int j = 0; j < M; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken()); // 치즈 및 공기 정보를 2차원 배열에 저장
            }
        }

        boolean flag = true; // 치즈가 모두 녹았는지 여부를 확인하는 변수
        int cnt = 0; // 치즈가 녹는 데 걸리는 시간을 저장

하는 변수

        while (flag) {
            checked = new boolean[N][M]; // 내부 공간 확인을 위한 boolean 배열 초기화
            dfs(0, 0); // 치즈의 외부 공간을 파악하기 위한 DFS 수행

            for(int i = 0; i < N; i++) { // 모든 위치를 순회하며
                for(int j = 0; j < M; j++) {
                    if(paper[i][j] == 1) counting(i, j); // 치즈가 있는 위치에서 공기와의 접촉 면 수를 계산
                }
            }

            int cheese = 0; // 녹은 치즈의 개수를 저장하는 변수
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(paper[i][j] > 1) { // 두 면 이상 공기와 접촉한 치즈라면
                        paper[i][j] = 0; // 해당 치즈를 녹임
                        cheese++; // 녹은 치즈 개수 증가
                    }
                }
            }

            if(cheese == 0) { // 녹을 치즈가 더 이상 없다면 시뮬레이션 종료
                flag = false;
                break;
            }

            cnt++; // 치즈가 모두 녹지 않았다면 시간을 증가시키고 다음 반복 수행
        }
        System.out.println(cnt); // 최종 결과 출력
    }

    // 치즈가 공기와 접촉한 면의 수를 계산하는 함수
    public static void counting(int r, int c) {
        int cnt = 0; // 공기와 접촉한 면의 수를 저장하는 변수

        for (int i = 0; i < 4; i++) { // 4방향으로 탐색 (상하좌우)
            int nr = r + dr[i]; // 새로운 행 위치
            int nc = c + dc[i]; // 새로운 열 위치

            if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue; // 지도를 벗어난 경우 건너뜀
            if(paper[nr][nc] == 0 && checked[nr][nc]) cnt++; // 공기와 접촉한 면이라면 cnt 증가
        }

        if(cnt >= 2) paper[r][c] = cnt; // 두 면 이상이 공기와 접촉한 경우 해당 위치를 녹일 준비
    }

    // 치즈 외부 공간을 파악하는 DFS 함수
    public static void dfs(int r, int c) {
        checked[r][c] = true; // 현재 위치를 방문 처리

        for (int i = 0; i < 4; i++) { // 4방향으로 탐색 (상하좌우)
            int nr = r + dr[i]; // 새로운 행 위치
            int nc = c + dc[i]; // 새로운 열 위치

            if(nr < 0 || nc < 0 || nr >= N || nc >= M || checked[nr][nc]) continue; // 지도를 벗어나거나 이미 방문한 경우 건너뜀
            if(paper[nr][nc] == 0) { // 외부 공기라면
                dfs(nr, nc); // 재귀 호출을 통해 탐색 계속
                checked[nr][nc] = true; // 탐색 완료 후 방문 처리
            }
        }
    }
}