[백준] 2636번 : 치즈 - 자바[Java]

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

2636번: 치즈

 

풀이

먼저 배열 값을 입력받을 때 치즈의 개수를 카운트해서 cheese에 저장한다.

그 다음 while문을 사용하여 cheese가 0이 될 때까지 BFS를 수행한다.

 

BFS는 배열의 처음 위치를 시작점으로 삼는다.

0인 경우에는 위치를 큐에 넣어 탐색을 계속하도록 하고, 1인 경우에는 해당 칸 값을 0으로 변경하고 cheese--를 한다.

 

코드

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

public class Main {
	
	static int[][] arr;
	static int n, m, cheese = 0;
	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());
    	
    	n = Integer.parseInt(st.nextToken());
    	m = Integer.parseInt(st.nextToken());
    	
    	arr = new int[n][m];
    	
    	for (int i = 0; i < n; i++) {
    		st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < m; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    			if (arr[i][j] == 1) {
    				cheese++;
    			}
    		}
    	}
    	
    	if (cheese == 0) {
    		System.out.println(0 + "\n" + 0);
    		return;
    	}
    	
    	int days = 0;
    	int cnt = 0;
    	
    	while(true) {
    		days++;
    		cnt = cheese;
    		bfs();
    		
    		if(cheese == 0) {
    			break;
    		}
    	}
    	System.out.println(days + "\n" + cnt);
    }
    
    public static void bfs() {
    	Queue<int[]> q = new LinkedList<>();
    	boolean[][] visited = new boolean[n][m];
    	q.add(new int[] {0,0});
    	visited[0][0] = true;
    	
    	while(!q.isEmpty()) {
    		int[] cur = q.poll();
    		int x = cur[0], y = cur[1];
    	
    		for (int idx = 0; idx < 4; idx++) {
    			int nx = x + dx[idx];
    			int ny = y + dy[idx];
    		
    			if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
    				visited[nx][ny] = true;
    				
    				if (arr[nx][ny] == 1) {
    					arr[nx][ny] = 0;
    					cheese--;
    				}
    				else if (arr[nx][ny] == 0) {
    					q.add(new int[] {nx, ny});
    				}
    			}
    		}
    	}
    	
    }
    
}

 

참고

• https://moonsbeen.tistory.com/227