[Algorithm] 백준 알고리즘 1012 (유기농 배추)

 

java 코드

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 Main {
	
	static int T, M, N, K;
	static int map[][];
	static boolean visited[][];
	static int count;
	static Queue<int[]> q = new LinkedList<>();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		
		while(T!=0) {
			st = new StringTokenizer(br.readLine());
			M=Integer.parseInt(st.nextToken());
			N=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			count=0;
			map = new int [M][N];
			visited = new boolean [M][N];
			
			while(K!=0) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[x][y]=1;
				K--;
			}
			
			for(int i=0; i<M; i++) {
				for(int j=0; j<N; j++) {
					
					if(map[i][j]==1) {
						q.add(new int[] {i,j});
						visited[i][j]=true;
						map[i][j]=0;
						count++;
						solve();
					}
				}
			}
			System.out.println(count);
			
			T--;
		}
	}
	static void solve() {
		int dx[] = {-1, 1, 0, 0};
		int dy[] = {0, 0, 1, -1};
		
		while(!q.isEmpty()) {
			int location[]=q.poll();
			int x = location[0];
			int y = location[1];
			for(int i=0; i<4; i++) {
				int xx=x+dx[i];
				int yy=y+dy[i];
				if(xx>=0&&xx<M&&yy>=0&&yy<N) {
					if(map[xx][yy]==1&&!visited[xx][yy]) {
						map[xx][yy]=0;
						visited[xx][yy]=true;
						q.add(new int[] {xx,yy});
					}
				}
			}
		}
	}
}