[BOJ] 1012. 유기농 배추

BaekJoon 1012. 유기농배추

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

[문제 접근]

방문 여부를 체크하는 배열을 만들어서 1로만 이루어진 덩어리들을 하나씩 세기만 하면 된다

 

 

 

 

 

 

[코드]

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

public class Main_10122 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); //테스트 케이스
		for (int test_case = 1; test_case <= T; test_case++) {
			int M = sc.nextInt(); //가로
			int N = sc.nextInt(); //세로
			int K = sc.nextInt(); //배추 개수
			int[][] map = new int[M][N];
			boolean[][] visit = new boolean[M][N]; //방문 체크

			for (int i = 0; i < K; i++) {
				map[sc.nextInt()][sc.nextInt()] = 1;
			}

			int warm = 0;
			
			Queue<Cord> queue = new LinkedList<>();
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 1 && !visit[i][j]) {
						visit[i][j] = true;
						queue.add(new Cord(i, j));
						
						while (!queue.isEmpty()) {
							Cord temp = queue.poll();
							
							int[] dx = {-1, 0, 1, 0};
							int[] dy = {0, -1, 0, 1};
							
							for (int l = 0; l < 4; l++) {
								int nx = temp.x + dx[l];
								int ny = temp.y + dy[l];
								
								if (nx >= 0 && nx < M && ny >=0 && ny < N) {
									if (map[nx][ny] == 1 && !visit[nx][ny]) {
										queue.add(new Cord(nx, ny));
										visit[nx][ny] = true;
									}
								}
							}
						}
						warm++;
					}
					
				}
				
			}
			System.out.println(warm);
		}
	}
	
	static class Cord{
		int x;
		int y;
		
		public Cord(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}