[BOJ] 1012번 유기농 배추

개요

오랜만에 풀어보는 2차원 배열 그래프 탐색 문제

문제링크

코드

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

public class Baekjoon1012 {
    public static int[][] dir = { {-1,0}, {1,0}, {0,-1}, {0,1} };
    public static int[][] farm;
    public static int m;
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            farm = new int[m][n];

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

                farm[x][y] = 1;
            }

            int count = 0;

            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if(farm[j][l] == 1) {
                        count++;
                        dfs(j, l);
                    }
                }
            }

            bw.write(count+"\n");
        }
        bw.flush();

        
    }

    public static void dfs(int x, int y) {
        farm[x][y] = -1;

        for (int i = 0; i < dir.length; i++) {
            int r = x + dir[i][0];
            int c = y + dir[i][1];

            if(r < 0 || c < 0 || r >= m || c >= n)
                continue;

            if(farm[r][c] == 1) {
                dfs(r, c);
            }
        }
    }

}

해결 과정

전체 2차원 배열안에서 배추가 모여있는 부분(1)을 카운트하는 문제이다.

2차원 배열의 크기가 엄청 크지 않으므로 전체 인덱스를 한번씩 확인해서 탐색하지 않고 배추가 있는 인덱스이면 DFS를 실행하고 카운트를 업해주는 방식으로 구현하였다. (굳이 DFS로 하지 않고 BFS로 해도 무방하다)

(DFS를 실행하면 인접한 모든 배추(1)를 확인하여 -1로 바꾸어준다)

이전에 풀었던 단지번호 매기기의 하위버전인 문제였다.

결과