[백준(Baekjoon)][자바(java)] 1012 : 유기농 배추 / 그래프와 순회

 

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

1012번: 유기농 배추

 

문제 풀이

 

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 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine()), n, m, k, i, j, d;
		StringTokenizer st;
		boolean[][] arr, visited;
		int cnt, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, pos[], x, y, nx, ny;
		Queue<int[]> queue; // x, y
		StringBuilder sb = new StringBuilder();
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			arr = new boolean[n][m];
			for (i = 0; i < k; ++i) {
				st = new StringTokenizer(br.readLine());
				arr[Integer.parseInt(st.nextToken())]
				   [Integer.parseInt(st.nextToken())] = true;
			}
			cnt = 0;
			visited = new boolean[n][m];
			queue = new LinkedList<>();
			for (i = 0; i < n; ++i) {
				for (j = 0; j < m; ++j) {
					if (arr[i][j] && !visited[i][j]) {
						cnt++;
						visited[i][j] = true;
						queue = new LinkedList<>();
						queue.add(new int[]{i, j});
						while (!queue.isEmpty()) {
							pos = queue.remove();
							x = pos[0];
							y = pos[1];
							for (d = 0; d < 4; ++d) {
								nx = x + dx[d];
								ny = y + dy[d];
								if (nx < 0 || nx >= n || 
									ny < 0 || ny >= m || 
									!arr[nx][ny] || 
									visited[nx][ny])
									continue;
								visited[nx][ny] = true;
								queue.add(new int[]{nx, ny});
							}
						}
					}
				}
			}
			sb.append(cnt + "\n");
		}
		br.close();
		
		System.out.println(sb.toString());
	}
}