[백준(Baekjoon)][자바(java)] 1012 : 유기농 배추 / DFS와 BFS

 

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int m, n, f[][];
	static boolean v[][];
	static int x_c[] = { 0, 1, 0, -1 }, y_c[] = { 1, 0, -1, 0 };  // 상하좌우 ( cross )
	
	public static void findNextCells_DFS( int x, int y ) {
		if( x < 0 || y < 0 || x >= n || y >= m )  return;
		if( v[x][y] )  return;
		v[x][y] = true;
		for( int k = 0; k < 4; k++ ) 
			findNextCells_DFS( x + x_c[k], y + y_c[k] );
	}
	
	public static int getCnt() {
    	int cnt = 0;
		for( int i = 0; i < n; i++ ) {
			for( int j = 0; j < m; j++ ) {
				if( !v[i][j] ) {
					DFS( i, j );
					cnt++; 
				}
			}
		}
        return cnt;
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		
		int t = Integer.parseInt( br.readLine() ), i, j;
		
		while( t-- > 0 ) {
			
			StringTokenizer st = new StringTokenizer( br.readLine() );
			m = Integer.parseInt( st.nextToken() );
			n = Integer.parseInt( st.nextToken() );
			int k = Integer.parseInt( st.nextToken() );
			
			f = new int[n][m];	// field arr
			for( i = 0; i < k; i++ ) {
				st = new StringTokenizer( br.readLine() );
				int x = Integer.parseInt( st.nextToken() );
				int y = Integer.parseInt( st.nextToken() );
				f[y][x]++;
			}
			
			v = new boolean[n][m];	// visited arr
			for( i = 0; i < n; i++ )
				for( j = 0; j < m; j++ )
					if( f[i][j] == 0 )
						v[i][j] = true;
			
			bw.append( getCnt() + "\n");
		}
		
		bw.flush();
		bw.close();	
	}
	
}