[백준 - 2638] 골드4 - 치즈 (bfs)

www.acmicpc.net/problem/2638

2638번: 치즈

1. 유형

bfs

 

2. 풀이

왼쪽 귀퉁이 부터 시작해서 bfs를 돌린다.

 

1인 부분을 만나면 check배열을 1 증가 시킨다

 

bfs가 끝난 후, check배열에서 값이 2 이상이면 map을 갱신한다.

 

3. 코드

package bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class back_2638치즈 {
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int n = Integer.valueOf(st.nextToken());
		int m = Integer.valueOf(st.nextToken());
		int map[][] = new int[n][m];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.valueOf(st.nextToken());
				sum = map[i][j] == 1 ? sum + 1 : sum;
			}
		}
		int time = 0;
		while (true) {
			if(sum==0) break;
			int check[][] = new int[n][m];
			boolean visit[][] = new boolean[n][m];
			Queue<int[]> q = new LinkedList<>();
			q.add(new int[] { 0, 0 });
			visit[0][0] = true;
			while (!q.isEmpty()) {
				int cur[] = q.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d];
					int nc = cur[1] + dc[d];
					if(nr<0 || nr>=n|| nc<0 ||nc>=m) continue;
					if(visit[nr][nc]) continue;
					if(map[nr][nc]==1) {
						check[nr][nc]++;
						continue;
					}
					visit[nr][nc] = true;
					q.add(new int[] {nr,nc});
				}
			}
			for(int i=0;i<n;i++) {
				for(int j=0; j<m; j++) {
					if(check[i][j]>1) {
						map[i][j]= 0;
						sum--;
					}
				}
			}
			time++;
		}
		System.out.println(time);
	}
}

 

핵심부분. 1인부분을 만나면 check증가. 나중에 이 부분이 2 이상이면 map을 0으로 바꾼다

					if(map[nr][nc]==1) {
						check[nr][nc]++;
						continue;
					}