백준 1012번: 유기농 양배추(Java, 그래프, DFS, BFS)

☑️ 문제

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

✔️관련 알고리즘 개념

깊이 우선 탐색

너비 우선 탐색

☑️ 문제 분석

• 해당 문제는 BFS 혹은 DFS 탐색을 진행하면서 탐색이 진행되는 그룹수를 구하면 된다.

☑️ 코드

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

public class Main {
    static int[][] visited;
    static Queue<Cabbage> queue = new LinkedList<>();
    static int T, M, N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken()); // 가로 길이 (열)
            N = Integer.parseInt(st.nextToken()); // 세로 길이 (행)
            K = Integer.parseInt(st.nextToken()); // 배추 위치 개수

            visited = new int[N][M];

            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken()); // 가로
                int y = Integer.parseInt(st.nextToken()); // 세로
                visited[y][x] = 1; // 좌표 저장
            }

            queue.clear();
            int count = 0;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < M; c++) {
                    if (visited[r][c] == 1) {
                        BFS(r, c);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    static void BFS(int r, int c) {
        visited[r][c] = 0;
        queue.add(new Cabbage(r, c));

        while (!queue.isEmpty()) {
            Cabbage cur = queue.poll();

            // 상
            if (cur.r - 1 >= 0 && visited[cur.r - 1][cur.c] == 1) {
                visited[cur.r - 1][cur.c] = 0;
                queue.add(new Cabbage(cur.r - 1, cur.c));
            }
            // 하
            if (cur.r + 1 < N && visited[cur.r + 1][cur.c] == 1) {
                visited[cur.r + 1][cur.c] = 0;
                queue.add(new Cabbage(cur.r + 1, cur.c));
            }
            // 좌
            if (cur.c - 1 >= 0 && visited[cur.r][cur.c - 1] == 1) {
                visited[cur.r][cur.c - 1] = 0;
                queue.add(new Cabbage(cur.r, cur.c - 1));
            }
            // 우
            if (cur.c + 1 < M && visited[cur.r][cur.c + 1] == 1) {
                visited[cur.r][cur.c + 1] = 0;
                queue.add(new Cabbage(cur.r, cur.c + 1));
            }
        }
    }

    static class Cabbage {
        int r, c;
        Cabbage(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 여기서 M은 가로(열), N은 세로(행)
• Java에서 배열은 arr[행][열] 구조라서 new int[N][M] 로 만들어야 한다
• 이전 코드에서는 x=가로, y=세로를 그대로 [x][y]에 넣고 있어서 index가 꼬인다.

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