채우다

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

• 풀이방법[알고리즘]

'단지번호붙이기'와 동일하게 DFS, BFS로 모두 풀 수 있는 문제. r,c 값을 쉽게 처리하기 위해 Point class를 만들었다. 배추의 위치를 r,c로 입력받으면서 map에서 해당 위치를 1로 표시하고, bfs를 돌린다. 이중 포문을 만들고, 한칸씩 이동하면서, map의 값이 1이고, 해당 위치가 방문된 적이 없는 경우 새로운 배추집단이므로 answer에 1을 더한후,  Queue에 넣고 퍼져나간다. Queue에 넣은 값들로부터 상하좌우 이동하면서 방문체크를 한 다음, 더이상 갈 곳이 없으면 큐에서 빠져나온다.

package newAlgorithm;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class P7_BJ1012 {
    static int T, M, N, K, answer, map[][];
    static int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};
    static boolean check[][];
    static Queue<Point> q;

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

        T = Integer.parseInt(st.nextToken());
        for (int t = T; t >0 ; t--) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            answer=0;
            map = new int[M][N];
            check = new boolean[M][N];

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                map[r][c]=1;
            }
            bfs();
            sb.append(answer).append("\n");
        }//tc
        System.out.println(sb);
    }//main

    static void bfs(){
        q = new ArrayDeque<>();

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j]==1 && !check[i][j]){
                    q.add(new Point(i,j));
                    answer++;
                    while(!q.isEmpty()){
                        Point tmp = q.poll();
                        if(check[tmp.r][tmp.c])continue;//이미 이전에 접근했으면 더 볼 필요 없음.
                        check[tmp.r][tmp.c]=true;
                        for (int k = 0; k < 4; k++) {
                            int nr = tmp.r+move[k][0];
                            int nc = tmp.c+move[k][1];
                            if(nr>=0 && nc>=0 && nr<M && nc<N && !check[nr][nc] && map[nr][nc]==1){   //맵 안에 있고, 아직 접근하지 않았고, map이 1이면
                                q.add(new Point(nr,nc));
                            }//if
                        }//for
                    }//while
                }
            }
        }
    }//bfs

    static class Point{
        int r;
        int c;
        public Point(int r, int c){
            this.r = r;
            this.c = c;
        }
        public String toString(int r, int c){
            return "r & c =" + r+"&"+c;
        }
    }
}//class