BOJ - 2636 ) 치즈

---

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

2636번: 치즈

 

---

그래프에 간선이 0과 1밖에 없는 경우 특정 시점에서 특정값을 구할때 0-1 BFS를 사용한다.

 

즉 몇번의 BFS를 통하여 모양이 만들어지는지? 약간말이 이상한데. 위 문제에서는 몇개의 C를 거치면 

 

map의 위치로 갈 수 있는지? 와 치즈가 녹는 시간은 동치이다.

 

0,0은 치즈가 없음이 보장되어있기에 이쪽에서 bfs를 시작해서 c를 만나면 덱에 뒤쪽에, c를만나지 않으면 덱의 

 

앞쪽에 넣어서 만난 c의개수가 적은것부터 처리하게 진행한다.

 

최종적으로 max와 max와 같은개수인 cnt가 정답인 문제.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 치즈 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int map[][] = new int[N][M];
		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());
			}
		}
		int res[][] = new int[N][M];
		int max = 0;
		int count = 0;
		boolean visit[][] = new boolean[N][M];
		ArrayDeque<int []> dq = new ArrayDeque<>();
		dq.addFirst(new int[] {0,0,0});
		visit[0][0] = true;
		int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
		while(!dq.isEmpty()) {
			int now[] = dq.poll();
			int y = now[0];
			int x = now[1];
			int cnt = now[2];
			for(int i = 0 ; i < 4 ; i ++) {
				int ny = y + dir[i][0];
				int nx = x + dir[i][1];
				if(ny >= 0 && nx >= 0 && ny < N && nx < M) {
					if(!visit[ny][nx]) {
						visit[ny][nx] = true;
						if(map[ny][nx] ==1) {
							res[ny][nx] = cnt+1;
							if(max < cnt+1) {
								max = cnt+1;
								count =0;
							} 
							if(max == cnt+1) {
								count++;
							}
							dq.addLast(new int[] {ny,nx,cnt+1});
						} else {
							dq.addFirst(new int[] {ny,nx,cnt});
						}
					}
				}
			}
		}
		System.out.println(max);
		System.out.println(count);
	}
}

---