알고리즘 | DFS | Java 백준[Silver II] 유기농 배추 - 1012

[Silver II] 유기농 배추 - 1012

문제 링크

성능 요약

메모리: 13552 KB, 시간: 96 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

제출 일자

2024년 9월 28일 00:27:07

문제 설명

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

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 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

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

풀이

이 문제는 DFS(깊이 우선 탐색)를 사용하여 배추흰지렁이가 필요한 최소 마리 수를 계산하는 문제입니다. 배추흰지렁이는 인접한 배추에 서식할 수 있으므로, 인접한 배추들끼리 연결된 그룹을 하나의 덩어리로 보고, 이러한 덩어리들의 수를 계산하는 것이 핵심입니다.

DFS 접근법

1. 문제 개요

• 배추밭에서 1은 배추가 심어진 곳, 0은 배추가 심어지지 않은 곳을 나타냅니다.
• 인접한 배추들이 서로 연결된 덩어리를 이루며, 각 덩어리에 배추흰지렁이 한 마리만 필요합니다.
• 우리는 배추들의 연결된 그룹을 찾아야 하며, 이를 DFS로 탐색하여 그룹 수를 계산합니다.

2. DFS 구현

• 각 배추를 방문하면서, 아직 방문하지 않은 배추를 만날 때마다 DFS로 그 배추와 인접한 배추들을 모두 탐색하여 하나의 그룹을 형성합니다.
• 이 과정에서 그룹이 발견될 때마다 흰지렁이 수를 1씩 증가시킵니다.

3. 알고리즘 흐름

• 주어진 배추밭을 이차원 배열로 표현하고, 각 좌표에서 배추가 심어져 있는지 확인합니다.
• DFS를 이용해 인접한 배추들을 모두 탐색하면서 방문한 배추는 다시 방문하지 않도록 처리합니다.
• 탐색이 끝나면 배추 그룹 수를 증가시키고, 모든 배추를 탐색할 때까지 이 과정을 반복합니다.

DFS 구현 흐름

1. 방문 체크 및 탐색

• 각 배추 위치에서 DFS를 시작하여 인접한 배추들을 모두 방문합니다.
• 상하좌우로 인접한 배추를 확인하여 탐색 범위를 확장합니다.

2. 탐색 종료 후 그룹 카운트

• DFS로 하나의 그룹이 완성되면 흰지렁이 수를 1 증가시킵니다.
• 이 과정을 배추밭의 모든 배추에 대해 반복합니다.

코드 설명

private static void DFS(int x, int y) {
    visited[y][x] = true; // 현재 배추를 방문 처리

    for (int direction = 0; direction < 4; direction++) {
        int nextY = y + dy[direction];
        int nextX = x + dx[direction];

        // 범위를 벗어나지 않았는지 확인
        if (nextX < 0 || nextY < 0 || nextX >= colLength || nextY >= rowLength) {
            continue;
        }

        // 아직 방문하지 않았고 배추가 심어져 있으면 DFS 계속 진행
        if (!visited[nextY][nextX] && field[nextY][nextX] == 1) {
            DFS(nextX, nextY);
        }
    }
}

최종 흐름

• solution 함수에서 전체 배추밭을 순회하며, 방문하지 않은 배추를 발견할 때마다 DFS를 호출하여 그 배추와 연결된 모든 배추를 방문합니다.
• 방문한 배추는 다시 방문하지 않도록 visited 배열로 체크하며, 각 DFS 호출마다 그룹 수를 증가시킵니다.

전체 코드

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

public class Main {

    private static final int[] dy = {-1, 1, 0, 0};
    private static final int[] dx = {0, 0, -1, 1};
    private static boolean[][] visited;
    private static int[][] field;
    private static int colLength;
    private static int rowLength;

    private static int solution() {
        int totalCount = 0;

        for (int row = 0; row < rowLength; row++) {
            for (int col = 0; col < colLength; col++) {
                if (visited[row][col]) {
                    continue;
                }
                if (field[row][col] == 1) {
                    DFS(col, row);
                    totalCount++;
                }
            }
        }
        return totalCount;
    }

    private static void DFS(int x, int y) {
        visited[y][x] = true;

        for (int direction = 0; direction < 4; direction++) {
            int nextY = y + dy[direction];
            int nextX = x + dx[direction];
            if (nextX < 0 || nextY < 0 || nextX >= colLength || nextY >= rowLength) {
                continue;
            }
            if (!visited[nextY][nextX] && field[nextY][nextX] == 1) {
                DFS(nextX, nextY);
            }
        }
    }

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

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

        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for (int testCase = 0; testCase < T; testCase++) {
            st = new StringTokenizer(br.readLine());
            colLength = Integer.parseInt(st.nextToken());
            rowLength = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            field = new int[rowLength][colLength];
            visited = new boolean[rowLength][colLength];
            for (int i = 0; i < rowLength; i++) {
                Arrays.fill(field[i], 0);
                Arrays.fill(visited[i], false);
            }
            for (int i = 0; i < target; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                field[y][x] = 1;
            }

            sb.append(solution()).append("\n");
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

[공부한 내용 중 고민했던 점]

문제는 간단히 정리했을 때 1로 연속적으로 연결된 부분의 개수를 구하면 되는 문제였는데, 가장 먼저 떠오른 것은 BFS이지만 이렇게 되면 Queue와 같은 자료구조를 직접 관리해 줘야 한다는 불편함이 있다고 생각했습니다. 즉, DFS를 활용해 재귀로 풀었을 때 더 간단한 코드가 나오지 않을까? 더 직관적이지 않을까라는 생각이 들었습니다.

DFS로 풀이할 것을 결정했을 때, 한 가지 걱정되는 것은 재귀적으로 너무 깊어진다면 스택오버플로가 발생할 수 있다는 것인데, 여기 문제에서는 50 x 50이 최대 넓이이므로 약 100만 번의 재귀 호출 스택 한도를 가진 자바에서는 괜찮을 것이라고 판단했습니다.