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

문제

✔ 난이도 - Silver 2

설명

bfs
오른쪽 -> 아래 -> 왼쪽 -> 위 순서대로 돌아가면서 검사
구역의 갯수를 구하면 그게 곧 배추흰지렁이의 갯수이다.

(0,0) 부터 시작하면서 검사 -> 1 마주치면 검사시작
검사하면 0으로 변경 (방문했다는 뜻)
Queue 활용해서 연결된 구역 다 방문하기

⚠️ 문제에서는 x, y 좌표로 표현하고있는데 우리는 배열로 계산할거니 뒤집어줘야한다
가로길이 10, 세로길이 8 이라는것은 -> Row가 8이고 Column이 10이라는 뜻
4 2 좌표가 1이라는 것은 -> row 2, column 4가 1이라는 뜻

풀이

public class Main {

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

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int Col = Integer.parseInt(st.nextToken());
            int Row = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[][] graph = new int[Row][Col];
            int[] dr = new int[] {0, 1, 0, -1};
            int[] dc = new int[] {1, 0, -1, 0};

            int count = 0;

            for (int i = 0; i < K; i++){
                st = new StringTokenizer(br.readLine());
                int c = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                graph[r][c] = 1;
            }
            // System.out.println(Arrays.deepToString(graph));
            // 입력받기 완료

            for (int i = 0; i < Row; i++){
                for (int j = 0; j < Col; j++){
                    if (graph[i][j] == 0) continue;
                    count++;

                    bfs(graph, i, j, dr, dc, Row, Col);
                }
            }
            sb.append(count).append("\n");
        }
        
        System.out.println(sb);
    }

    private static void bfs(int[][] graph, int i, int j, int[] dr, int[] dc, int Row, int Col){
        Queue<int[]> queue = new LinkedList<>();
        graph[i][j] = 0;
        queue.offer(new int[] {i, j}); // 현재 row, col 저장

        while (!queue.isEmpty()){
            int[] node = queue.poll();
            int cr = node[0];
            int cc = node[1];

            for (int d = 0; d < 4; d++){
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                if (nr < 0 || nc < 0 || nr >= Row || nc >= Col || graph[nr][nc] == 0) continue;

                graph[nr][nc] = 0; // 방문표시
                queue.offer(new int[] {nr, nc});
            }
        }
    }
}

⏰ 시간복잡도

$O(N^2)$

1. 전체 스캔: 바깥쪽 중첩 for문이 모든 칸($M \times N$)을 한 번씩 훑음
2. BFS 탐색: while문 내에서 배추가 있는 모든 칸은 딱 한 번씩만 큐에 들어가고 0으로 바뀐다. 즉, 모든 while문의 실행 횟수를 다 합쳐도 전체 배추 칸 수($K$)를 넘지 못함.
   -> 결국 전체 칸을 한 번씩 다뤄보는 수준에서 끝나기 때문에, 격자 크기에 비례하는 $O(M \times N)$ 복잡도

$K$(배추 개수)는 상관없나?

입력 조건에 $K \le 2500$이라고 되어 있는데, $K$는 항상 $M \times N$보다 작거나 같을 수밖에 없다. 따라서 $K$가 아무리 많아져도 시간 복잡도는 격자 크기인 $O(M \times N)$에 갇히게 됨.

중첩 루프지만 누적으로 따지면 $O(N^2)$이다.