56 삐약 : 백준 1012| 유기농 배추 [바킹독 문제 풀이|BFS|JAVA]

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

 

        for(int c =0; c<T; c++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[][] input = new int[M][N];
            int[][] visited = new int[M][N];


            int count=0;
            while(K--> 0){
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                input[X][Y]=1;

            }


            for(int i=0;i<M;i++){
                for(int j=0; j<N;j++){
                    if( input[i][j] == 1 && visited[i][j]!=1){
                        Queue<Pair> q = new LinkedList<Pair>();
                        q.add(new Pair(i,j));

                        while(!q.isEmpty()){
                            Pair p = q.poll();

                            visited[p.X][p.Y] = 1;

                            for(int k=0;k<4;k++){
                                int nx = p.X+dx[k];
                                int ny = p.Y+dy[k];


                                if(nx>=0 && nx <M && ny>=0 && ny<N){
                                    if(visited[nx][ny]!=1 && input[nx][ny]==1){
                                        q.add(new Pair(nx,ny));
                                        visited[nx][ny] =1;
                                    }
                                }

                            }
                        }
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

 

 

 

이전에 풀었던 방식과 비슷하게 생각하면 쉽게 풀리는 문제이다.