[백준/Java] 1012 : 유기농 배추(BFS)

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

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Baekjoon_1012_유기농배추_BFS {

	static int M, N, K;
	static int[][] map;
	static boolean[][] check;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int TC = sc.nextInt();

		for (int tc = 1; tc <= TC; tc++) {

			M = sc.nextInt();
			N = sc.nextInt();
			K = sc.nextInt();
			map = new int[N][M];
			check = new boolean[N][M];
			
			for (int i = 0; i < K; i++) {			
				int y = sc.nextInt();
				int x = sc.nextInt();
				map[x][y] = 1;
			}

			int cnt = 0;
			Queue<Point> que = new LinkedList<Point>();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] == 1 && !check[i][j]) {
						cnt++;
						que.add(new Point(i, j));
						check[i][j] = true;
						
						while(!que.isEmpty()) {
							Point tmp = que.poll();					
							for (int k = 0; k < 4; k++) {
								int nx = tmp.x + dx[k];
								int ny = tmp.y + dy[k];						
								if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == 1 && !check[nx][ny]) {
									que.add(new Point(nx, ny));
									check[nx][ny] = true;
								}
							}
						}
					}
				}
			}
			System.out.println(cnt);
		}
		sc.close();
	}
}

class Point {
	int x;
	int y;
    
	point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}