[백준 1012] 유기농 배추 Java 풀이

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

 

접근

DFS 또는 BFS를 이용하여 배추 그룹의 수를 구합니다. 배추 그룹의 수는 곧 필요한 배추흰지렁이의 마리 수를 의미하기 때문에 문제를 해결할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int m, n, k;
	static boolean[][] map;
	static boolean[][] visited;

	// 동, 서, 남, 북
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder result = new StringBuilder();
		StringTokenizer st;

		// 입력 처리
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());

			map = new boolean[n][m];
			visited = new boolean[n][m];

			while (k-- > 0) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[y][x] = true;
			}

			// dfs로 필요한 최소의 배추흰지렁이 마리 수를 구한다.
			int count = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[i][j] && !visited[i][j]) {
						count++;
						visited[i][j] = true;
						dfs(i, j);
					}
				}
			}

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

		// 결과 출력
		System.out.println(result);
	}

	static void dfs(int y, int x) {
		for (int dir = 0; dir < 4; dir++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (inRange(ny, nx) && map[ny][nx] && !visited[ny][nx]) {
				visited[ny][nx] = true;
				dfs(ny, nx);
			}
		}
	}

	static boolean inRange(int y, int x) {
		return 0 <= y && y < n && 0 <= x && x < m;
	}
}