[백준/java] 2636. 치즈

문제 링크 - https://www.acmicpc.net/problem/2636

🌱 문제

---

🌱 풀이

다음 두 과정을 반복하면 된다.
종료 조건은 치즈가 남아있지 않을때 까지 이다.
1. bfs 돌리면서 치즈가 아닌 부분이면서 공기(바깥)과 이어지는 좌표 -1로 업데이트하기.
2. 현재 치즈가 있는 좌표중에 인접한 칸(동서남북)이 공기인 좌표 -1로 업데이트

---

메인 함수의 while문

• 앞에서 설명한 그대로 1번,2번 과정을 반복하고 치즈가 남아있지 않으면 break로 종료한다.

while (true) {
			if (existCheese() == 0) // 남은 치즈가 없으면  while문 끝내기 
				break;
			bfs(0, 0); //공기와 접촉된 칸 -1로 채우기  (0,0)은 가장자리라 항상 공기로 취급되니까 (0,0)으로 bfs돌리기 
			simulate(); // 공기와 접촉한 좌표 -1로 채우는 함수 
			answer++; // 시간 1 증가 

		}

		System.out.println(answer);
		System.out.println(cheeseCnt);

---

bfs

• 앞에서 설명한 1번과정에 해당한다.
• bfs는 공기(바깥)과 이어지는 좌표를 찾는 과정인데 가장자리는 무조건 공기(바깥) 취급 되므로 가장자리 중 아무 좌표인(0,0) 지점부터 bfs를 시작하도록 하였다.

public static void bfs(int r, int c) {
		boolean visited[][] = new boolean[R + 1][C + 1];
		Queue<Point> queue = new ArrayDeque<Point>();
		visited[r][c] = true;
		queue.add(new Point(r, c));

		while (!queue.isEmpty()) {
			Point cur = queue.poll();
			for (int d = 0; d < 4; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.c + dc[d];

				if (nr >= 0 && nc >= 0 && nr < R && nc < C) {
					if (visited[nr][nc] == false && arr[nr][nc] != 1) {
						arr[nr][nc] = -1;
						visited[nr][nc] = true;
						queue.add(new Point(nr, nc));
					}
				}
			}

		}
	}

---

남은 치즈 갯수 계산

• 다음 함수는 단순히 2차원배열의 모든좌표를 돌면서 치즈 갯수를 세는 함수이다.

public static int existCheese() { // 남아있는 치즈 갯수 리턴
		int cnt = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (arr[i][j] == 1)
					cnt++;
			}
		}

		if (cnt == 0)
			return 0;
		return cheeseCnt = cnt;
	}

---

공기와 인접(동서남북)한 좌표 치즈 없애주기.

• 앞에서 설명한 2번 과정에 해당한다.
• 치즈가 있는 지점중에서 인접(동서남북)한 좌표중 공기가 있으면치즈가 사라질 좌표이므로 -1으로 업데이트 해주었다.
• 이때 주의할점은 2중포문을 돌면서 인접한 좌표가 공기일때마다 바로 arr[i][j]=-1로 좌표를 수정하면 안되고, 리스트에 치즈를 없애줄(=-1로 갱신할 예정일) 좌표를 담아 놓고 한번에 처리해야 한다는것이다.
  if(인접한 좌표가 공기면) arr[i][j]=-1과 같이 그때그때 처리하면 다음 처리해야할 좌표를 구할 때 이전 상태를 잃어버리게 되므로 올바른 값이 나오지 않게된다.

public static void simulate() {
		ArrayList<Point> list = new ArrayList<Point>();
		// 치즈가 녹아 없어질 예정일 좌표들 list에 담아놓기
		for (int i = 1; i < R - 1; i++) {
			for (int j = 1; j < C - 1; j++) {
				if (arr[i][j] == 1) {
					if ((arr[i - 1][j] == -1) || (arr[i][j - 1] == -1) || (arr[i + 1][j] == -1)
							|| (arr[i][j + 1] == -1))
						list.add(new Point(i, j));
				}
			}
		}
		//리스트에 담긴 좌표들 -1로 갱신 
		for (Point cur : list) {
			arr[cur.r][cur.c] = -1;
		}
	}

---

🌱 코드

package week07.boj_2636;

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

//2636. 치즈 (주석추가) 
public class Somyeong {
	static class Point {
		int r;
		int c;

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

		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}

	}

	static int R, C, cheeseCnt, answer;
	static int arr[][];
	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));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		arr = new int[R][C];

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		while (true) {
			meetAir(0, 0); //공기와 접촉된 칸 -1로 채우기  (0,0)은 가장자리라 항상 공기로 취급되니까 (0,0)으로 bfs돌리기 
			
			if (existCheese() == 0) // 남은 치즈가 없으면  while문 끝내기 
				break;

			simulate(); // 공기와 접촉한 좌표 -1로 채우는 함수 
			answer++; // 시간 1 증가 

		}

		System.out.println(answer);
		System.out.println(cheeseCnt);

	}

	public static void meetAir(int r, int c) {
		boolean visited[][] = new boolean[R + 1][C + 1];
		Queue<Point> queue = new ArrayDeque<Point>();
		visited[r][c] = true;
		queue.add(new Point(r, c));

		while (!queue.isEmpty()) {
			Point cur = queue.poll();
			for (int d = 0; d < 4; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.c + dc[d];

				if (nr >= 0 && nc >= 0 && nr < R && nc < C) {
					if (visited[nr][nc] == false && arr[nr][nc] != 1) {
						arr[nr][nc] = -1;
						visited[nr][nc] = true;
						queue.add(new Point(nr, nc));
					}
				}
			}

		}
	}

	public static int existCheese() { // 남아있는 치즈 갯수 리턴
		int cnt = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (arr[i][j] == 1)
					cnt++;
			}
		}

		if (cnt == 0)
			return 0;
		return cheeseCnt = cnt;
	}

	public static void simulate() {
		ArrayList<Point> list = new ArrayList<Point>();
		// 치즈가 녹아 없어질 예정일 좌표들 list에 담아놓기
		for (int i = 1; i < R - 1; i++) {
			for (int j = 1; j < C - 1; j++) {
				if (arr[i][j] == 1) {
					if ((arr[i - 1][j] == -1) || (arr[i][j - 1] == -1) || (arr[i + 1][j] == -1)
							|| (arr[i][j + 1] == -1))
						list.add(new Point(i, j));
				}
			}
		}
		//리스트에 담긴 좌표들 -1로 갱신 
		for (Point cur : list) {
			arr[cur.r][cur.c] = -1;
		}
	}

}