All :L

[BOJ/Java] 치즈 (2638) 본문

CODING/BOJ

[BOJ/Java] 치즈 (2638)

ofijwe 2024. 8. 29. 15:10
반응형

치즈 (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; // 탐색 완료 후 방문 처리
            }
        }
    }
}
반응형

'CODING > BOJ' 카테고리의 다른 글

[BOJ/Java] 농장 관리 (1245)  (0) 2024.08.29
[BOJ/Java] 양 한마리... 양 두마리... (11123)  (0) 2024.08.29
[BOJ/Java] 섬의 개수 (4963)  (0) 2024.08.28
[BOJ/Java] 음식물 피하기 (1713)  (0) 2024.08.28
[BOJ/Java] 듣보잡 (1764)  (0) 2024.08.28
'CODING/BOJ' Related Articles more
Comments