[BOJ] [JAVA] 1012번 유기농 배추

1012번: 유기농 배추

BFS를 이용해서 해결했다.

BFS의 개념 자체는 어렵지 않은데, 코드를 깔끔히 구현하는 방법을 모르겠다.

내가 생각한대로 코드를 작성해봤다.

좌표값을 Queue에 집어넣어야하는데, 방법을 모르고 qX, qY로 x, y 좌표를 각각 받았다.

Point라는 걸로 받으면 된다더라,,

그리고 나는 현재 depth에서 확인해야 할 노드의 개수를 그 전 depth에서 계산하고,

다음 depth에게 알려주는 방식으로 했는데 정석이 어떤지는 확인해봐야겠다!

package BOJ;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for (int t = 0; t < T; t++) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			int k = sc.nextInt();
			
			int [][] farm = new int[n][m];
			
			for (int i = 0; i < k; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				
				farm[y][x] = 1;
			}
			
			int [] di = {1, -1, 0, 0};
			int [] dj = {0, 0, 1, -1};
			
			int ans = 0;
			
			Queue<Integer> qX;
			Queue<Integer> qY;
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (farm[i][j] == 1) {
						farm[i][j] = -1; // visit
						
						ans++; // if visit
						
						qX = new ArrayDeque<>();
						qY = new ArrayDeque<>();
						
						qX.offer(i); // initial value
						qY.offer(j);
						
						int nodes; // check nodes
						int cnt = 1;
						
						while (true) {
							nodes = cnt;
							cnt = 0;
							while (nodes != 0) {
								for (int d = 0; d < 4; d++) {
									int ni = qX.peek() + di[d];
									int nj = qY.peek() + dj[d];
									if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
										if (farm[ni][nj] == 1) {
											qX.offer(ni);
											qY.offer(nj);
											cnt++;
											farm[ni][nj] = -1;
										}
									}
								}
								qX.poll();
								qY.poll();

								nodes--;
							}
							if (qX.isEmpty()) break;
						}
					}
				}
			}
			System.out.println(ans);
		}
	}
}