[백준] 1012번: 유기농 배추 (Java)

문제: https://www.acmicpc.net/problem/1012번

📌 문제 탐색하기

입력 : 첫째 줄 - 테스트 케이스 개수 T
두번째 줄 - 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50) / 세로길이 N(1 ≤ N ≤ 50) / 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)
K줄 - 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)
출력 : 각 T에 대해 필요한 배추흰지렁이 마리 수

가능한 시간복잡도

O(V + E)
V : 정점의 수
E : 간선의 수

알고리즘 선택

DFS

📌 코드 설계하기

1. 테스트 케이스의 수 T를 입력받고, 각 T마다 밭의 크기 M (가로)와 N (세로), 배추의 수 K를 입력받는다.
2. 배추가 심어진 위치를 표시하는 2차원 배열인 field와 각 위치의 방문 여부를 기록하는 2차원 배열인 visited를 생성한다.
3. 배추가 심어진 위치를 field 배열에 표시한다.
4. DFS를 이용해 특정 위치에서 시작하여 상하좌우로 연결된 배추들을 모두 방문 표시한다.
5. 방향 벡터 dx와 dy를 이용하여 네 방향으로 탐색한다.
6. 모든 위치를 순회하며 배추가 있고 방문하지 않은 경우, DFS를 시작하여 연결된 그룹을 모두 방문 표시한다.
7. DFS를 시작할 때마다 그룹 수를 하나씩 증가시킨다.
8. 각 T에 대해 필요한 배추흰지렁이 마리 수를 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.Scanner;

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

    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();
            int K = sc.nextInt();

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

            for (int i = 0; i < K; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                field[x][y] = 1;
            }

            int count = 0;
            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);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

        sc.close();
    }

    private static void dfs(int x, int y) {
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};

        visited[x][y] = true;

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (field[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }
}