문제

풀이

1. 배추를 1으로 두고 배추의 위치들을 리스트에 저장
2. 배추 위치 순차적으로 탐색하는데 방문 배열이 0이면 bfs 실행

   ---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            st=new StringTokenizer(br.readLine());
            int m=Integer.parseInt(st.nextToken());
            int n=Integer.parseInt(st.nextToken());
            int k=Integer.parseInt(st.nextToken());
            int[][] map=new int[n][m];
            ArrayList<int[]> ones=new ArrayList<>();
            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[y][x]=1;
                ones.add(new int[]{y,x});
            }
            int[][] v=new int[n][m];
            int cnt=0;
            for(int[] one:ones){
                int y=one[0];
                int x=one[1];
                if(v[y][x]==0){
                    bfs(map,v,y,x,n,m);
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }

    static void bfs(int[][] map,int[][] v,int y,int x,int n,int m){
        int[][] d=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{y,x});
        while(!q.isEmpty()){
            int[] now=q.poll();
            for(int i=0;i<4;i++){
                int dy=now[0]+d[i][0];
                int dx=now[1]+d[i][1];
                if(dy<0||dx<0||dy>=n||dx>=m)continue;
                if(map[dy][dx]==1&&v[dy][dx]==0){
                    q.add(new int[]{dy,dx});
                    v[dy][dx]=1;
                }
            }
        }
    }
}

#bfs