백준 1012(유기농 배추)

문제

코드

성공 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Init
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for(int t = 0; t < testCase; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());

            //init
            int map[][] = new int[m][n];
            boolean visit[] = new boolean[m * n];
            for (int i = 0; i < cnt; i++) {
                StringTokenizer tmp = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(tmp.nextToken());
                int y = Integer.parseInt(tmp.nextToken());
                map[y][x] = 1;
            }

            Arrays.fill(visit, true);

            List<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
            for(int i = 0; i < n * m; i++)
                list.add(new ArrayList<>());

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int value = map[i][j];
                    int position = (i * n) + j;

                    if (value == 1)
                        visit[position] = false;

                    if (j != n - 1) {// 마지막 열 제외
                        list.get(position).add(position + 1);
                        list.get(position + 1).add(position);
                    }
                    if (i != m - 1) {// 마지막 행 제외
                        list.get(position).add(position + n);
                        list.get(position + n).add(position);
                    }
                }
            }


            Queue<Integer> queue = new LinkedList<>();
            List<Integer> result = new ArrayList<>();
            for(int i = 0; i < n * m; i++){
                if(visit[i]) continue;

                queue.offer(i);
                int cntTmp = 0;
                while (!queue.isEmpty()){
                    int ing = queue.poll();
                    for(int j = 0; j < list.get(ing).size(); j++){
                        int next = list.get(ing).get(j);
                        if(!visit[next]){
                            visit[next] = true;
                            queue.offer(next);
                            cntTmp++;
                        }
                    }
                }
                result.add(cntTmp);
            }

            System.out.println(result.size());
        }
    }
}