[BAEKJOON] - 1012번 : 유기농 배추

1012번 문제 링크

📜 알고리즘 접근 방법

해당 문제는 DFS 알고리즘을 통해 접근이 가능한 문제입니다.

주어진 탐색 범위가 최대 50으로 작기 때문에 O(N^2)으로 탐색을 수행해도 문제 없습니다.

dfs 알고리즘을 선택한 이유는 문제의 인접 노드에 '1' 이라는 값이 있는지 여부를 따져서 차지하는 범위를 알아야 하기 때문에 '1'이 있는 곳으로 깊이 탐색을 수행해야 합니다.

이는 깊이 탐색이 나뉘는 분기(section) 를 기준으로 횟수를 새어 주면 쉽게 풀 수 있는 dfs 구현 문제입니다.

👾 구현

import java.util.*;
import java.io.*;

public class Main {
    static int m, n;
    static boolean[][] visited;
    static boolean[][] area;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

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

        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        StringTokenizer st;

        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken()); // 가로
            n = Integer.parseInt(st.nextToken()); // 세로
            area = new boolean[n][m];
            visited = new boolean[n][m];

            int k = Integer.parseInt(st.nextToken()); // 배추 갯수

            int count = 0;
            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                area[y][x] = true;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visited[i][j] && area[i][j]) {
                        count++;
                        dfs(i, j);
                    }
                }
            }
            sb.append(count).append("\n");
        }

        br.close();

        System.out.println(sb);
    }

    static void dfs(int c, int r) {
        visited[c][r] = true;
        for (int i = 0; i < 4; i++) {
            int row = dr[i] + r;
            int col = dc[i] + c;

            if (row < 0 || col < 0 || row >= m || col >= n)
                continue;

            if (!visited[col][row] && area[col][row]) {
                dfs(col, row);
            }
        }
    }
}