[백준] 1012번. 유기농 배추(JAVA)

문제

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

---

풀이(25분)

import java.io.*;
import java.util.*;
public class Main {

    static boolean[][] originArr;
    static Queue<Point> queue;
    static int[][] direction = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder(); // 스트링 빌더를 활용한 출력
        int n = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < n; i++){
            queue = new LinkedList<>();
            st = new StringTokenizer(br.readLine());
            int rowSize = Integer.parseInt(st.nextToken());
            int colSize = Integer.parseInt(st.nextToken());
            int cabbage = Integer.parseInt(st.nextToken());
            originArr = new boolean[rowSize][colSize];
            for(int j = 0; j < cabbage; j++){
                st = new StringTokenizer(br.readLine());
                int row = Integer.parseInt(st.nextToken());
                int col = Integer.parseInt(st.nextToken());
                originArr[row][col] = true;
            }
            int answer = 0;
            for(int x = 0; x < rowSize; x++){
                for(int y = 0; y < colSize; y++){
                    if(originArr[x][y]){
                        queue.add(new Point(x,y));
                        originArr[x][y] = false;
                        bfs(rowSize,colSize);
                        answer++;
                    }
                }
            }
            sb.append(answer + "\n");
        }

        System.out.println(sb);


    }

    public static void bfs(int rowSize, int colSize){
        while(!queue.isEmpty()){
            Point p = queue.poll();
            int row = p.row;
            int col = p.col;
            for(int i = 0; i < 4; i++){
                int tempRow = row + direction[i][0];
                int tempCol = col + direction[i][1];
                if(tempRow >= 0 && tempRow < rowSize && tempCol >= 0 && tempCol < colSize){
                    if(originArr[tempRow][tempCol]){
                        queue.add(new Point(tempRow, tempCol));
                        originArr[tempRow][tempCol] = false;
                    }
                }
            }
        }
    }

    public static class Point{
        int row;
        int col;

        public Point(int row, int col){
            this.row = row;
            this.col = col;
        }
    }
}

 

간단한 bfs/dfs 문제라고 생각했다. 추가적으로 방문한 처리만 제대로 해주면 되고 그에 따라 값을 물고다니는 것이 없기때문에 난이도는 낮다고 생각한다.