Point 💡

BFS 함수를 자바로 처음 작성해봤다.

주요 키워드는 다음과 같다!

Queue<int[]> queue = new LinkedList<>(); // LinkedList로 구현
q.offer(new int[] {0,0}); // q에 원소 넣기, 큐 차있을 때 false 반환
q.poll(); // q에서 원소 빼기
q.add(new int[] {nx, ny}); // q에 원소 넣기, 큐 차있을 때 에러 반환

• 자바는 && 를 사용해서 조건문을 다 분리시켜 작성해야함

📌 설계

처음에는 어떻게 치즈의 테두리만을 파악하지? 라는 생각을 했다.

치즈가 중심이 아니라 공기를 중심으로 탐색을 해야한다!

공기부터 시작해서 탐색하다가 **1이 나오면 0으로 변환시키고, visited = True로 변경**한다. 2로 변환하기도 하는데, 굳이 그럴필요가 없었다.

이미 방문했으므로 0으로 바꿔도 그 노드가 큐에 들어갈일이 없으므로 테두리만 0으로 변경된다.

이 BFS 과정을 치즈가 모두 없어질때까지 반복한다.

My Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G2636 {

	static int n, m;
	static int cheese;
	static int[][] graph;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {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());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		// 전체 치즈의 개수를 구한다.
		graph = new int[n][m];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
				// 전체 치즈의 개수를 구한다.
				if (graph[i][j] == 1) cheese++;
			}
		}

		int cheeseCnt = 0;
		int time = 0;
		while (cheese != 0) {
			cheeseCnt = cheese;
			time ++;
			visited = new boolean[n][m];
			bfs();
		}

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

	public static void bfs() {
		Queue<int[]> q = new LinkedList<>();
		// 판 가장자리에는 치즈가 놓여있지않다고 했으므로 (0,0) 부터 시작
		q.offer(new int[] {0, 0});
		visited[0][0] = true;

		while(!q.isEmpty()) {
			int[] current = q.poll();

			for (int i =0; i < 4; i++) {
				int nx = current[0] + dx[i];
				int ny = current[1] + dy[i];

				if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
					visited[nx][ny] = true;
					if (graph[nx][ny] == 0) {
						// add : 큐가 꽉 찬 경우 에외 발생 시킴
						// offer : 추가 실패를 의미하는 false 리턴
						q.add(new int[] {nx, ny});
					} else {
						cheese --;
						// 이미 방문했으므로 치즈를 0으로 바꿔도 탐색하지 않는다.
						graph[nx][ny] = 0;
					}
				}
			}
		}

	}
}