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

접근 방법 🧐

나는 dfs, bfs가 너무 어렵다..
우선 어떤 방법으로 풀어야할지도 감이 안 잡혀서 다른 분들의 글을 보다가 내 나름대로 기준을 정해봤다.
나만의 DFS BFS 판단 방법!

• 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 된다
  → 인접한 배추끼리 한 그룹으로 묶인다.
  
  
• 한 배추의 상하좌우 방향에 다른 배추가 위치하면 인접한 것이다.
  →dx, dy배열

내가 쓴 코드 ✍️

import java.util.*;
import java.io.*;

public class Main {
	
	static int[][] map;
	static boolean[][] visited;
	static int M, N, K;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int cnt;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder result = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=0;t<T;t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[M][N];
			visited = new boolean[M][N];
			cnt = 0;
			
			for(int i=0;i<K;i++) { //배추 위치 넣어줌
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[x][y] = 1;
			}
			
			for(int i=0;i<M;i++) {
				for(int j=0;j<N;j++) {
					if(map[i][j]==1&&!visited[i][j]) {
						dfs(i,j);
						cnt++;						
					}
				}
			}
			result.append(cnt+"\n");
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		for(int i=0;i<4;i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx >=0&&ny>=0&&nx<M&&ny<N&&!visited[nx][ny]&&map[nx][ny]==1) {
				dfs(nx,ny);
			}
		}
	}
}

느낀점 📖

비슷한 문제인 단지번호붙이기 문제도 있다.

경로를 찾기 보다는 모든 곳을 다 돌면서 그룹을 지어줘야하니, dfs를 이용해서 풀었다. 처음에 T 테스트케이스가 2이상일 수도 있는데, 안일하게 당연히 한 번인 줄 알고, 반복문을 하나 덜 했었다.
어쩐지 예제 입력1 중간에 숫자 3개 있는 line이 두 번 나오더라 🙃