[JAVA] 백준 1012 유기농 배추

[백준 1012]https://www.acmicpc.net/problem/1012

문제 조건

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우 서로 인접해있다고 함.
인접한 배추당 지렁이 하나가 필요.
-> 인접한 배추 그룹의 수를 세는 문제 : 그래프 연결 요소 문제이지 않을까

---

문제 입력

1. 첫 줄에 테스트 케이스 개수 T 입력
2. 다음 줄부터 테스트 케이스에 대해 첫 줄에 배추밭의 가로길이 M, 세로길이 N, 배추가 심어진 위치의 개수 K 입력
3. 그 다음 K줄에 배추의 위치 x, y 입력

---

문제 풀이

1. 입력값을 토대로 2차원배열 생성
2. (0, 0) 위치부터 dfs(bfs도 상관 없음) 해서 새로 dfs 할 때마다 count +1
3. 테스트 케이스 횟수만큼 반복

---

문제 코드

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


public class Main {
    static boolean[][] farm;	// 배추밭 저장할 배열
    static boolean[][] isVisit;	// 방문여부 체크하는 배열
    static int m;
    static int n;
    static int k;
    static int[] nx = {0, 0, -1, 1};	// x 상하좌우
    static int[] ny = {1, -1, 0, 0};	// y 상하좌우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            farm = new boolean[n][m];
            isVisit = new boolean[n][m];

            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine(), " ");

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                farm[y][x] = true;
            }

            int count = 0;

            for (int y = 0; y < n; y++) {
                for (int x = 0; x < m; x++) {
                    if (!isVisit[y][x] && farm[y][x]) {
                        dfs(x, y);
                        count++;	// 처음 방문하는 경우 count++
                    }
                }
            }

            sb.append(count).append('\n');
        }

        System.out.println(sb);
    }

    private static void dfs(int x, int y) {
        isVisit[y][x] = true;

        for (int i = 0; i < 4; i++) {
            int newX = x + nx[i];
            int newY = y + ny[i];

	// 배열 인덱스를 넘지 않기 위한 조건
            if ((newX >= 0 && newY >= 0) && (newX < m && newY < n)) {
                if (!isVisit[newY][newX] && farm[newY][newX]) {
                    dfs(newX, newY);
                }
            }
        }
    }

}

---

처음 문제 풀 때 실수해서 너무 오래걸렸다. 배열의 인덱스가 (0, 0) <= (x, y) <(m, n)인 걸 생각하고 어차피 처음인 (0, 0)부터 반복할테니 좌표의 네 방향이 아니라 우측 방향(x + 1, y)과 하측 방향(x, y + 1)만 방문 체크 하면 될 것 같았는데 dfs 재귀호출하면서 탐색을 안하는 불상사가 생겼다. 실수를 줄이기 위해서 설계를 좀 더 확실하게 해야할듯