[백준/JAVA] 2636_치즈

백준🔗

2636번: 치즈

 

문제

 

 

 

간단 풀이

문제 상황 자체는 쉬웠는데 안쪽에 있는 공간과 바깥에 있는 공간을 어떻게 구분해야 할 지 고민이 됐다.

그래서 생각해낸 풀이는

1) BFS를 수행하며 치즈 바깥 공간을 -1로 바꾼다.

2) 가장자리에 있는 치즈를 찾아서 2로 바꾼다. (2차원 배열을 전부 탐색하며 상하좌우로 -1이 하나라도 있으면 가장자리 치즈라고 판단)

3) 다시 한 번 전체 탐색을 하며 2를 -1로 바꾸면서(가장자리에 있는 치즈 녹이기) 1인 개수를 세서 남은 치즈 조각을 카운트한다.

4) 남은 치즈 조각이 0이 될 때까지 1~3 과정을 반복한다.

 

뭔가 복잡한 듯 싶긴 했지만.. 시간 복잡도를 생각해봤을 때 1번 과정이 O(4*가로*세로) (각각의 칸에서 상하좌우에 대해 탐색) , 2번과 3번 과정이 각각 O(가로*세로)이기 때문에 한 시간에 한 번 치즈를 녹이는 데에 6*O(가로*세로) 만큼의 시간이 소요되고, 가로, 세로가 최대 100이기 때문에 충분히 제한 시간 내로 해결할 수 있겠다고 판단했다.

 

그렇게 아래의 코드를 작성했고, 문제를 통과했다!!

 

그런데 문제를 풀고 난 후 다른 사람들의 코드를 열어보니, 더 단순하게 풀이가 가능했다.

1번에서 BFS를 수행하면서 현재 칸에 대해 방문처리를 한 후, 해당 칸이 0이면 큐에 넣고 1이면 0으로 만드는 식으로 진행을 하면 내 풀이의 2, 3번과 같은 과정을 할 필요가 없었다!!

BFS 한 번 만으로 가장자리의 치즈만 녹일 수 있는 것이다. 

 

그러나 한 가지 의문인 것은.. 나의 풀이와 위의 BFS 한 번으로 치즈를 녹이는 풀이의 실행 시간이 차이가 없다는 것이다..🧐🧐 왜일까... 

 

코드

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

public class Main {
	static int M, N;
	static int[][] board;
	static boolean[][] visited;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 세로 길이
		N = Integer.parseInt(st.nextToken()); // 가로 길이
		board = new int[M][N];
		int cnt = 0; // 치즈 조각이 놓여 있는 칸의 개수 카운트
		for (int r = 0; r < M; r++) {
			String input = br.readLine();
			for (int c = 0; c < N; c++) {
				board[r][c] = input.charAt(2 * c) - '0';
				if (board[r][c] == 1)
					cnt++;
			}
		}
		// 치즈가 모두 녹아 없어질 때까지 반복
		int prevCnt = 0;
		int time = 0;
		while (cnt != 0) {
			time++;
			prevCnt = cnt;
			cnt = 0;
			// 1) 치즈 바깥은 전부 -1로 채우기
			BFS();
			// 2) 전체 탐색하면서 가장자리 치즈는 2로 바꾸기
			findEdge();
			// 3) 다시 한 번 전체 탐색하면서 2인 곳은 -1로 만들어주고(치즈 녹이기), 남은 치즈 조각 cnt하기
			for (int r = 0; r < M; r++) {
				for (int c = 0; c < N; c++) {
					if (board[r][c] == 2)
						board[r][c] = -1;
					else if (board[r][c] == 1)
						cnt++;
				}
			}
		}

		System.out.println(time);
		System.out.println(prevCnt);
	}

	static class Pos {
		int r, c;

		public Pos(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	// 치즈 바깥쪽은 -1로 채우기
	static void BFS() {
		visited = new boolean[M][N];
		Queue<Pos> q = new LinkedList<>();
		q.add(new Pos(0, 0));
		board[0][0] = -1;
		visited[0][0] = true;
		while (!q.isEmpty()) {
			Pos cur = q.poll();
			for (int d = 0; d < 4; d++) {
				int rr = cur.r + dr[d];
				int cc = cur.c + dc[d];
				if (!outOfRange(rr, cc) && board[rr][cc] != 1 && !visited[rr][cc]) {
					board[rr][cc] = -1;
					visited[rr][cc] = true;
					q.add(new Pos(rr, cc));
				}
			}
		}
	}

	// 공기와 접촉한 치즈들 2라고 표시하기
	static void findEdge() {
		for (int r = 0; r < M; r++) {
			for (int c = 0; c < N; c++) {
				if (board[r][c] == 1 && isEdge(r, c))
					board[r][c] = 2;
			}
		}
	}

	static boolean outOfRange(int r, int c) {
		return r < 0 || r >= M || c < 0 || c >= N;
	}

	// 치즈가 가장자리에 있는 공기와 접촉된 치즈인지 판단
	static boolean isEdge(int r, int c) {
		for (int d = 0; d < 4; d++) {
			int rr = r + dr[d];
			int cc = c + dc[d];
			// 판의 가장 바깥쪽 테두리에는 치즈가 없기 때문에 배열 범위 벗어날 일은 없음!
			if (board[rr][cc] == -1)
				return true;
		}
		return false;
	}
}

 

참고 자료