[백준] 1012 유기농 배추 자바

문제 출처 : https://www.acmicpc.net/problem/1012

접근방법

일단 필자는 입력 코드의 예제가 크지않다면, 이해를 위해 도식화 하는 편이다.
따라서, 해당 문제도 도식화 하게 되었습니다.
배추 위치의 x,y

0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6

를 입력 받을 경우를 도식화 해보자.
그럼 여기서 카운팅을 하면 되는 것이다.

참고로 이 도식화는 이런 식으로 하라는 예시에 불과합니다.
위 도식화에서, 인접배열(리스트)에서 인접한 경우가 1인 경우에 카운트 1을 하라는 것이 아닙니다. {(0,1),(1,1),(1,0)} 중에서 아무 군데나 흰지렁이를 푼다면, 다 안전한 것입니다.
또한, {(4,2)(4,3)} 둘 중 하나, (2,4)(3,4) 둘 중 하나, (4,5)에 1개,
{(7,4)~(9,5)}중 아무거나 한 군데에 놓게 되면 다 안전한 것입니다.

즉,
0은 길이 막혀져있고, 1은 연결되어있는 길이라고 생각하면 쉽습니다.
따라서, 1은 연결되어있는 통로니까 자연스레 지나갈 수 있고, 0은 못가서 cnt++를 해주는 것이라고 이해하면 쉽습니다.

만약, 필자의 설명이 부족하다면, 좀더 자세히 도식화된 설명을 보여주는 좋은 블로깅을 하신 분의 링크를 남기겠습니다. --> https://lotuus.tistory.com/98

코드

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

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

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

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

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

            for (int k = 0; k < K; k++) {
                st = new StringTokenizer(br.readLine());
                int y = Integer.parseInt(st.nextToken());
                int x = Integer.parseInt(st.nextToken());
                field[x][y] = 1;
            }

            count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (dfs(i, j)) {
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    public static boolean dfs(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M || visited[x][y] || field[x][y] == 0) {
            return false;
        }

        visited[x][y] = true;

        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);

        return true;
    }
}