[백준] 1012번 : 유기농 배추(JAVA)

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

1012번: 유기농 배추

---

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 28단계

 

DFS와 BFS의 카테고리에 포함되어 있는 문제이다.

 

처음부터 끝가지 검사하면서 배추가 심어져있으면 상하좌우로 모두 연결된 배추를

 

BFS로 검사하고 방문표시를 넣음과 동시에 카운트를 센다.

 

처음에는 큐에 좌표를 입력하는 동시에 방문표시를 내는걸 몰라서

 

시간초과가 났었다.

 

다음부터는 조심해서 코딩해야겠다.

 

import java.util.*;

public class Quesiton_1012 {

	static int dx[] = {1, 0, -1, 0};
	static int dy[] = {0, 1, 0, -1};
	static int M, N, K;
	static int map[][];
	static boolean visit[][];
	
	public static void bfs(int x, int y) {
		Queue<Integer> qx = new LinkedList<Integer>();
		Queue<Integer> qy = new LinkedList<Integer>();
		
		qx.add(x);
		qy.add(y);
		
		while(!qx.isEmpty() && !qy.isEmpty()) {
			x = qx.poll();
			y = qy.poll();
			visit[x][y] = true;
			
			for (int i = 0; i < 4; i++) {
				int _x = x + dx[i];
				int _y = y + dy[i];
				
				if(_x >= 0 && _y >= 0 && _x < M && _y < N) {
					if(map[_x][_y] == 1 && visit[_x][_y] == false) {
						qx.add(_x);
						qy.add(_y);
						visit[_x][_y] = true;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int i = 0; i < T; i++) {
			int count = 0;
			
			M = sc.nextInt();
			N = sc.nextInt();
			K = sc.nextInt();
			
			map = new int[M][N];
			visit = new boolean[M][N];
			
			for(int j = 0; j < K; j++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				
				map[x][y] = 1;
			}
			
			for(int k = 0; k < M; k++) {
				for(int l = 0; l < N; l++) {
					if(map[k][l] == 1 && visit[k][l] == false) {
						bfs(k, l);
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
}