[백준] 치즈 2636 - JAVA

문제

https://www.acmicpc.net/problem/2636

2636번: 치즈

풀이

BFS 탐색 알고리즘을 사용하여 문제를 풀었다.

 

우선, 현재 치즈의 개수를 세어 준 다음 치즈 개수가 0이 아닐때까지 BFS 탐색을 하며 치즈의 개수를 줄여나갔다. 탐색은 0,0부터 시작하여 치즈를 만나면 해당 치즈를 없애주고, 치즈가 아니라면 큐에 넣어 근처에 있는 치즈를 탐색하도록 하였다.

코드

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

public class Main {
	static int r, c;
	static int board [][];
	static int cheese;
	
	static int dx [] = {-1, 0, 1, 0};
	static int dy [] = {0, -1, 0, 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());
		
		board = new int[r+1][c+1];
		
		cheese = 0;
		for(int i=1;i<=r;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=c;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				
				if(board[i][j] == 1)
					cheese++;
			}
		}
		
		int hour = 0;
		int result = 0;
		while(cheese != 0) {
			hour++;
			result = cheese;
			bfs();
		}
		
		System.out.println(hour);
		System.out.println(result);
		
	}

	   
	static void bfs() {
		Queue <int[]> que = new LinkedList<>();
		boolean visited [][] = new boolean [r+1][c+1];
		
		
		que.add(new int[] {1, 1});
		visited[1][1] = true;
		
		while(!que.isEmpty()) {
			int [] cur = que.poll();
			
			for(int t=0;t<4;t++) {
				int nx = cur[0] + dx[t];
				int ny = cur[1] + dy[t];
				
				if(nx < 1 || ny < 1 || nx > r || ny > c) continue;
				if(visited[nx][ny]) continue;
				
				if(board[nx][ny] == 1) {
					cheese--;
					board[nx][ny] = 0;
				}
				else if(board[nx][ny] == 0) {
					que.add(new int[] {nx, ny});
				}
				visited[nx][ny] = true;	
			}
		}
		
	}
}