[BOJ/Java] 2636. 치즈

[BOJ/Java] 2636. 치즈

2636번: 치즈

---

문제 해석

이 문제는 치즈가 테두리부터 녹아 없어지는 과정을 시뮬레이션하는 문제다. NxM 크기의 격자에 치즈(1로 표시된 부분)가 놓여 있으며, 치즈의 외부 공간은 0으로 표시된다. 치즈는 격자의 가장자리에 노출된 면이 있는 경우, 한 시간 후에 녹아 없어진다. 문제의 목적은 치즈가 모두 녹아 없어지는 데 걸리는 시간과 마지막으로 녹기 전 남은 치즈의 개수를 구하는 것이다.

풀이 과정

1. 격자의 크기와 초기 상태를 입력 받는다.
2. 외부 공간에서 시작하는 BFS를 수행하여 치즈의 가장자리에 위치한 부분을 찾는다. 이를 위해 격자의 (0, 0)에서 시작해 0으로 연결된 모든 부분을 탐색한다.
3. 방문 중 1을 만나면 그 위치를 delList에 추가하여 이후 녹일 치즈의 위치로 기록한다.
4. 한 번의 BFS가 끝나면 delList에 저장된 모든 치즈를 녹이고 (map의 해당 위치를 0으로 변경), 녹인 치즈의 수를 ans에 저장한다.
5. delList가 비어 있지 않은 동안 위 과정을 반복하며, 녹인 치즈가 없을 때까지 걸린 시간과 마지막으로 녹은 치즈의 개수를 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No2636;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().io();
	}

	private int c;  // 격자의 열 크기
	private int r;  // 격자의 행 크기
	private int[][] map;  // 격자 상태를 나타내는 2차원 배열
	private int ans;  // 마지막으로 녹은 치즈의 수
	private ArrayList<Point> delList;  // 녹을 치즈의 위치를 저장하는 리스트
	private static final int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };  // 이동 방향 (상하좌우)

	private void io() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new int[r][c];
		
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < c; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs(0, 0);  // 외부 공간에서 BFS 시작
		int time = 0;
		while(delList.size() != 0) {
			time++;
			bfs(delList.get(0).x, delList.get(0).y);  // 녹은 치즈의 위치에서 다음 BFS 실행
		}
		
		sb.append(time).append("\n").append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private void bfs(int x, int y) {
		Queue<Point> queue = new ArrayDeque<>();
		boolean[][] visited = new boolean[r][c];
		queue.offer(new Point(x, y));
		visited[x][y] = true;
		delList = new ArrayList<>();
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			for (int d = 0; d < direction.length; d++) {
				int nx = p.x + direction[d][0];
				int ny = p.y + direction[d][1];
				
				if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
				
				if(visited[nx][ny]) continue;
				
				if(map[nx][ny] == 0) {
					visited[nx][ny] = true;
					queue.offer(new Point(nx, ny));
				}
				
				if(map[nx][ny] == 1) {
					visited[nx][ny] = true;
					delList.add(new Point(nx, ny));  // 치즈가 녹을 위치 추가
				}
			}
		}
		
		if(delList.size() == 0) return;
		
		for(Point p: delList) {
			map[p.x][p.y] = 0;  // 치즈 녹이기
		}
		
		ans = delList.size();  // 마지막으로 녹은 치즈의 수 저장
	}
	
	class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

시간 복잡도 분석

이 문제에서는 격자 전체를 탐색해야 하므로 최악의 경우 BFS를 수행할 때마다 O(R*C)의 시간이 소요된다. 각 BFS는 delList가 비어 있지 않은 동안 반복되므로, 전체 시간 복잡도는 O(K*R*C)가 될 수 있다. 여기서 K는 BFS가 수행되는 횟수다.

느낀점

치즈가 녹는 과정을 시뮬레이션하는 이 문제는 외부 공간에서의 BFS 접근 방식과 관련하여 깊은 이해를 필요로 한다. 문제의 요구사항을 정확히 이해하고, 효율적인 탐색 방법을 선택하는 것이 중요하다는 점을 다시 한번 깨닫게 되었다.