백준 1012 유기농 배추 (Java)

1. 문제 링크

1012번: 유기농 배추

 

2. 문제 및 입출력예제

 

3. 문제 풀이

배추가 나오면 bfs를 시작해서 인접한 배추를 전부 방문처리한다.

bfs를 한 번 할 때마다 배추의 개수를 증가한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static int N, M, K;
	static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	static boolean[][] map, visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			int result = 0;
			String[] split = br.readLine().split(" ");
			M = Integer.parseInt(split[0]);
			N = Integer.parseInt(split[1]);
			K = Integer.parseInt(split[2]);
			map = new boolean[N][M];
			visit = new boolean[N][M];
			for(int i=0;i<K;i++) {
				split = br.readLine().split(" ");
				int a = Integer.parseInt(split[0]);
				int b = Integer.parseInt(split[1]);
				map[b][a] = true;
			}
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(map[i][j] && !visit[i][j]) {
						result++;
						bfs(i, j);
					}
				}
			}		
			sb.append(result).append("\n");
		}
		System.out.println(sb);
	}

	private static void bfs(int i, int j) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] {i, j});
		visit[i][j] = true;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			int x = now[0];
			int y = now[1];
			for(int d=0;d<4;d++) {
				int X = x+dx[d];
				int Y = y+dy[d];
				
				if(X<0 || X>=N || Y<0 || Y>=M || visit[X][Y] || !map[X][Y]) {
					continue;
				}
				
				queue.offer(new int[] {X, Y});
				visit[X][Y] = true;
			}
		}
	}
}