[알고리즘] 백준 1012 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_1012 {
    static int t;
    static int m;
    static int n;
    static int k;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s, " ");
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            // init map
            map = new int[m][n];
            visited = new boolean[m][n];

            for (int j = 0; j < m; j++) {
                Arrays.fill(map[i], 0);
            }

            for (int j = 0; j < k; j++) {
                s = br.readLine();
                st = new StringTokenizer(s, " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }

            List<Integer> list = new ArrayList<Integer>();

            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (map[j][l] == 1 && !visited[j][l]) {
                        int value = dfs(j, l);
                        list.add(value);
                    }
                }
            }
            System.out.println(list.size());
        }

    }

    public static int dfs(int x, int y) {
        int value = 1;
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            if (x + dx[i] >= 0 && x + dx[i] < m && y + dy[i] >= 0 && y + dy[i] < n) {
                if (map[x + dx[i]][y + dy[i]] == 1 && !visited[x + dx[i]][y + dy[i]])
                    dfs(x + dx[i],y + dy[i]);
            }
        }
        return value;
    }
}

어떤 배추가 있는 자리에서 인접한 상하좌우값을 탐색하여 배추군의 개수를 구하는 문제이다.

 

이 문제 같은 경우에는 입력 T만큼 테스트케이스가 여러 개 존재 하기 때문에 주의해야 한다.

 

T를 버퍼리더를 통해 받은 후 아래 코드 전부를 T만큼 반복수행 하도록 하였다.

 

DFS를 수행할 때는 상하좌우의 인덱스값을 검증한 후 배추가 존재하며 visited값이 false일 경우 재귀를 타도록 구현하였다.

 

끝으로 배추군의 숫자를 세기 위해 DFS값을 반환받을 때마다 List에 그를 추가하여 카운트하였다.

 

이 문제같은 경우에는 굳이 list를 쓸 필요 없이 그냥 int count를 하나 선언해서 해도 괜찮긴하다.

 

bfs로 풀어도 된다~