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

문제

배추 밭에 배추가 있는 곳과 없는 곳이 존재할 때

배추흰지렁이가 몇 마리 있어야 배추가 존재하는 곳에

해충이 들지 않게 할 수 있는지 구하라

 

배추흰지렁이가 있는 배추가 하나라도 존재하면

지렁이는 상하좌우 한 칸 이내에 인접한 배추로 옮겨 다닐 수 있다.

 

접근 방식

서로 끊어지지 않고 이어져 있는 배추라면

지렁이가 모두 해충을 처리할 수 있기 때문에

서로 이어진 배추들이 총 몇 개인지 확인하면 된다.

 

즉 서로 인접하지 않은 출발점들이 몇 개인지 확인하면 되는 문제로

이전에 풀었던 1926번 그림 문제와 같은 방식으로 풀 수 있다.

 

풀이

public class Main {

	private static StringTokenizer st;
	private static int m;
	private static int n;
	private static int cabbage;
	private static int[][] field;
	private static boolean[][] isVisited;
	private static int[] dx = {1, 0, -1, 0};
	private static int[] dy = {0, 1, 0, -1};
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			cabbage = Integer.parseInt(st.nextToken());

			field = new int[n][m];
			isVisited = new boolean[n][m];

			for (int j = 0; j < cabbage; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				field[y][x] = 1;
			}

			Queue<Pair> queue = new ArrayDeque<>();

			int count = 0;

			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					if (field[j][k] == 0 || isVisited[j][k]) continue;

					count++;
					queue.offer(new Pair(j, k));
					isVisited[j][k] = true;

					while (!queue.isEmpty()) {
						Pair cur = queue.poll();

						for (int dir = 0; dir < 4; dir++) {
							int nx = cur.x + dx[dir];
							int ny = cur.y + dy[dir];

							if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
							if (isVisited[nx][ny] || field[nx][ny] == 0) continue;

							queue.offer(new Pair(nx, ny));
							isVisited[nx][ny] = true;
						}
					}
				}
			}

			sb.append(count).append("\n");
		}

		System.out.println(sb);
	}

	private static class Pair {
		int x;
		int y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}