[백준 1012 : JAVA] 유기농 배추 / DFS

개요

 

기본적인 DFS, BFS를 통해 단절된 구역의 개수를 구하는 문제이다.

 

이 문제는 다음 문제와 비슷하며 이 문제를 먼저 풀고 다음 문제를 풀어보길 추천한다.

이 문제에서 약간 추가된 부분이 있는 문제이다.

 

2020/01/30 - [알고리즘/백준] - [백준 2667 : JAVA] 단지번호붙이기 / DFS

[백준 2667 : JAVA] 단지번호붙이기 / DFS

 

문제

 

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

입력

 

풀이

 

DFS를 이용한다. dfs(int x, int y)메소드는 다음과 같이 동작한다. 

 

1. 현재 노드를 방문처리한다.
2. 현재 노드에서 상, 하, 좌, 우의 노드로 갈 수 있는지 확인한다.(이때 범위의 초과여부, 배추의 존재여부를 확인한다.)
   1. 갈 수 있다면 dfs()메소드를 호출한다
3. 2를 반복하며 더이상 갈 수 있는 노드가 없을 때까지 반복한다.

메인 메소드에서 dfs호출 하나가 종료되면 구역이 1개라고 생각하고 풀이한다.

 

 

코드

 

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

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static boolean arr[][];
    static boolean check[][];
    static int m, n;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int textCnt = Integer.parseInt(br.readLine());
        int ans;

        for(int i = 0; i < textCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());

            arr = new boolean[n][m];
            check = new boolean[n][m];

            ans = 0;

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

                // x == col, y == row
                arr[y][x] = true;
            }

            for(int j = 0; j < n; j++){
                for(int k = 0 ; k < m; k++){
                    if(checkLocation(j, k) == true) {
                        ans++;
                        dfs(j, k);
                    }
                }
            }

            sb.append(ans + "\n");
        }

        System.out.println(sb);
    }
    public static boolean checkLocation(int row, int col){
        //좌표 값이 잘못된 경우
        if(row < 0 || row >= n || col < 0 || col >= m) return false;
        //이미 지나간 경로인 경우 || 집이 아닌 경우
        if(check[row][col] == true || arr[row][col] == false) return false;
        return true;
    }
    public static void dfs(int x, int y){
        check[x][y] = true;
        // '상'의 좌표
        if(checkLocation(x - 1, y)) dfs(x - 1, y);
        // '우'의 좌표
        if(checkLocation(x, y + 1)) dfs(x, y + 1);
        // '하'의 좌표
        if(checkLocation(x + 1, y)) dfs(x + 1, y);
        // '좌'의 좌표
        if(checkLocation(x, y - 1)) dfs(x, y - 1);
    }

}