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

---

문제 정보

• 문제 링크: https://www.acmicpc.net/problem/1012
• 문제 번호: 1012번
• 문제 이름: 유기농 배추
• 문제 난이도: 실버2
• 반복 학습 날짜
  • 2024.01.16 완료

1012번: 유기농 배추

---

코드

import java.util.Scanner;

public class Main {
    static int M, N, K;
    static int[][] field;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt(); // 테스트 케이스 수

        for (int t = 0; t < T; t++) {
            M = sc.nextInt(); // 가로 길이
            N = sc.nextInt(); // 세로 길이
            K = sc.nextInt(); // 배추 개수

            field = new int[M][N];
            visited = new boolean[M][N];

            // 배추의 위치 입력 받아서 필드에 표시
            for (int k = 0; k < K; k++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                field[x][y] = 1; // 배추가 심어진 위치를 표시
            }

            int result = 0;

            // 모든 위치에 대해 DFS 수행하여 배추 그룹 개수 구하기
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (field[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j); // DFS 수행
                        result++;
                    }
                }
            }

            System.out.println(result); // 결과 출력
        }
    }

    // DFS를 이용하여 배추 그룹 찾기
    static void dfs(int x, int y) {
        // 범위를 벗어나거나 이미 방문한 곳이면 종료
        if (x < 0 || x >= M || y < 0 || y >= N || field[x][y] == 0 || visited[x][y])
            return;

        visited[x][y] = true; // 방문 표시

        // 상하좌우에 대해 DFS 수행
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);
    }
}

---

풀이

Step1: DFS를 이용한 배추 그룹 찾기

// DFS를 이용하여 배추 그룹 찾기
static void dfs(int x, int y) {
    // 범위를 벗어나거나 이미 방문한 곳이면 종료
    if (x < 0 || x >= M || y < 0 || y >= N || field[x][y] == 0 || visited[x][y])
        return;

    visited[x][y] = true; // 방문 표시

    // 상하좌우에 대해 DFS 수행
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}

유기농 배추 문제는 DFS를 활용하여 배추 그룹을 찾는 문제입니다. 이전에 풀었던 바이러스 문제와 유사한 형태로 푸시게 된다면 쉽게 해결할 수 있습니다.

 

이 문제에서 가장 핵심 부분은 DFS를 활용한 배추 그룹을 찾는 부분으로 순서는 다음과 같습니다.

1. DFS는 특정 위치에서 시작하여 상, 하, 좌, 우로 이동하며 배추가 심어진 곳을 찾습니다.
2. 좌표(x, y)가 전체 크기에 대한 범위를 벗어나거나 배추가 심어지지 않았거나 방문을 했던 곳이라면 리턴합니다.
3. 그 외의 경우 해당 좌표에 대해 방문 표시를 한 후 해당 좌표에서 상, 하, 좌, 우 DFS함수를 호출합니다.
4. 연결되어 있는 배추들은 하나의 그룹으로 묶이게 되고 모든 그룹을 구하여 결과로 출력합니다.

위 문제에서 시간복잡도는 모든 좌표에 대해 한 번씩 무조건 방문하므로 O(M*N)이 됩니다.

 

*참고: 이전에 작성했던 "바이러스"문제를 참고하시면 더욱 쉽게 해결할 수 있습니다.