백준 2636 치즈 자바

 

package backjon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int N,M;
	static int[][] arr;
	static boolean[][] visited;
	
	static ArrayDeque<int[]> q;
	
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	
	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());

		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());
			}
		}
		
		int count = 0;
		int nCnt = 0;
		while(true) {			
			count++;
			
			bfs(0,0);
			
			boolean check = false;
			nCnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(arr[i][j] == -1) nCnt++;
					if(arr[i][j] == 1) {
						check = true;
						break;
					}
				}
				if(check) break;
			}
			if(!check) {
				break;
			}
		}
		
		System.out.println(count);
		System.out.println(nCnt);
	}

	private static void bfs(int i, int j) {
		visited = new boolean[N][M];
		q = new ArrayDeque<>();
		q.add(new int[] {i,j});
		visited[i][j] = true;

		while(!q.isEmpty()) {
			int[] move = q.poll();
			for (int k = 0; k < 4; k++) {
				int ny = move[0] + dy[k];
				int nx = move[1] + dx[k];
				
				if(ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx]) continue;
				visited[ny][nx] = true;
				if(arr[ny][nx] == 1) {
					arr[ny][nx] = -1;
					continue;
				}
				if(arr[ny][nx] == -1) {
					arr[ny][nx] = 0;					
				}
				q.add(new int[] {ny,nx});
				
			}
		}
	}


}

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

2636번: 치즈

 

접근 아이디어

외곽 치즈가 한 시간마다 사라지니 치즈가 없는 부분에서 bfs탐색을 시도하고 치즈를 만나면 continue를 하는 걸로 접근했다. 이 문제의 경우 1시간 전 치즈를 계산해야 하므로 치즈를 만났다면 바로 0으로 바꾸지 않고 -1이라는 값으로 바꾸고 모든 배열을 탐색했을 때 -1만 존재하면 다음 턴에 치즈가 사라지므로 -1만 존재할 때까지 탐색을 진행했다.

 

 

잘한 부분

bfs탐색과 1초가 남았을 때를 대비해서 -1로 바꿔주는 부분 계산을 금방 떠올렸다.

 

 

부족한 부분

치즈를 만나면 continue를 했어야 했는데 break를 적어서 디버깅하는데 정말 많은 시간이 걸렸다.