[Java] 백준 2636 : 치즈

1. 문제

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

2636번: 치즈

 

 

 

2. 풀이 과정

bfs나 dfs 아무거나 편한 걸로 선택해서 풀면 되는 문제 같다. 아래 풀이에서는 돌아본 곳을 또 방문하지 않기 위해서 bfs를 썼다. 무조건 바깥 테두리엔 치즈가 없으므로, 테두리 0, 0에서 시작해서 1을 만나면 값을 0으로 바꾸고 Queue에 쌓아주었다. 또 다음 Queue의 요소를 돌면서 또 1을 만나면 같은 작업을 반복해주었다. 하지만 N, M의 크기가 작은 편이라 전범위 탐색을 반복하는 것과 10ms정도밖에 차이나지 않았다..

그리고 총 치즈 칸 수에서 매번 cnt를 빼면서 치즈가 다 없어졌는지 + 마지막에 남아있던 치즈의 개수를 확인하였다.

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

public class Main {
	
	static int N, M, map[][], cnt;
	static boolean visited[][];
	static Queue<int[]> next;
	
	public static void bfs(Queue<int[]> q) {
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		while(!q.isEmpty()) {
			int pos[] = q.poll();
			for(int i=0; i<4; i++) {
				int nx = pos[0] + dx[i];
				int ny = pos[1] + dy[i];
				if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny]) {continue;}
				visited[nx][ny]=true;
				if(map[nx][ny]==1) {
					next.add(new int[] {nx, ny});
				}
				else {
					q.add(new int[] {nx, ny});
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M];
		cnt = 0;
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				cnt+=map[i][j];
			}
		}
		
		int hour = 0;
		Queue<int[]> now = new LinkedList<>();
		now.add(new int[] {1, 1});
		next = new LinkedList<>();
		while(cnt>0) {
			hour++;
			bfs(now);
			cnt-=next.size();
			now = next;
			next = new LinkedList<>();
		}
		System.out.println(hour+"\n"+now.size());
	}
	
}

 

결과