[자바] 백준 1012 : 유기농 배추 / 그래프 + DFS 풀이

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

1012번: 유기농 배추

실버2 난이도의 정답률 38% 문제입니다.

그래프 + DFS(혹은 BFS) 알고리즘으로 해결할 수 있습니다.

 

---

문제 분석 및 풀이

문제는 간단합니다. 배추밭의 가로와 세로 길이가 주어집니다.

그리고, 배추가 심어진 위치가 주어집니다.

​

배추가 심어진 위치는 1의 값을 가지며, 연결된 부분에 해충을 하나 풀면 연결된 부분은 해충 해결이 됩니다.

​

문제에서는 이렇게 연결된 부분의 개수를 찾으면 그것이 필요한 배추흰지렁이의 마리 수이고 이건 결국 정답이 됩니다.

​

이 문제는 보통 그래프의 정보가 주어지는 문제와 다르게 그래프를 직접 만들어야합니다.

​

만드는 방법은

처음에 주어지는 가로와 세로의 길이로 그래프 만들고, 모두 0으로 초기화 시켜줍니다.

그 후에 입력되는 좌표값 부분을 1로 바꿔주면 그래프가 만들어집니다.

​

그래프를 만들고 나서 dfs로 탐색을 하면서 영역을 찾아주면 해결이 됩니다.

 

 

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static int n, m, k;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] pos = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static int answer = 0;

    public static void main(String[] args) {
        int test = sc.nextInt();
        for (int i = 0; i < test; i++) {
            getAnswer();
        }
    }

    private static void getAnswer() {
        initData();
        searchMap();
        System.out.println(answer);
    }

    private static void initData() {
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[m][n];
        visited = new boolean[m][n];
        k = sc.nextInt();
        answer = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = 0;
            }
        }

        for (int i = 0; i < k; i++) {
            int node1 = sc.nextInt();
            int node2 = sc.nextInt();
            map[node2][node1] = 1;
        }
    }

    private static void searchMap() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    visited[i][j] = true;
                    dfs(i, j);
                    answer++;
                }
            }
        }
    }

    private static void dfs(int row, int col) {
        for (int i = 0; i < pos.length; i++) {
            int nr = row + pos[i][0];
            int nc = col + pos[i][1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && map[nr][nc] == 1) {
                visited[nr][nc] = true;
                dfs(nr, nc);
            }
        }
    }
}