1012번 - 유기농 배추

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

public class Main {
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static void dfs(int[][] map, int r, int c, int N, int M) {
		map[r][c] = 0;
		int nr, nc;
		for(int i=0;i<4;i++) {
			nr = r + dr[i];
			nc = c + dc[i];
			if(nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 1) {
				dfs(map, nr, nc, N, M);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for(int t=0;t<T;t++) {
			st = new StringTokenizer(br.readLine());
			int sum = 0;
			int M = Integer.parseInt(st.nextToken());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int[][] map = new int[N][M];
			int r, c;
			for(int i=0;i<K;i++) {
				st = new StringTokenizer(br.readLine());
				c = Integer.parseInt(st.nextToken());
				r = Integer.parseInt(st.nextToken());
				map[r][c] = 1;
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(map[i][j] != 0) {
						dfs(map, i, j, N, M);
						sum++;
					}
				}
			}
			sb.append(sum+"\n");
		}
		System.out.print(sb);
		br.close();
	}
}

이차원 배열에서 상하좌우로 연결된 그룹이 몇 개인지 묻는 문제입니다. 여기서는 전체 격자를 순회하면서 1이 발견되면 dfs를 돌려서 상하좌우로 연결된 1을 모두 0으로 만드는 방식으로 진행했습니다.

 

dfs의 경우 클래스에 사방이동을 위한 dr과 dc배열을 선언해서 처음 호출된 위치로부터 상하좌우를 체크(가능한 범위 안인지, 해당 격자가 1인지)하고 1이 있을 경우 탐색을 이어가는 방식으로 구현했습니다.

 

dfs로 한 번에 찾아지는 모든 격자들이 하나의 그룹으로 취급되기 때문에 메인에서 dfs를 호출할 때마다 출력할 답에 1씩 더해주면 문제가 해결됩니다.