[백준 / Java] 1012번 유기농 배추

사용한 알고리즘 (DFS)

DFS 

https://cobi-98.tistory.com/30

[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

 

해당 문제는 단지 번호 붙이기의 문제를 풀었다면 더 쉽게 풀었을 문제인 것 같다.

https://cobi-98.tistory.com/33

 

이제 문제를 확인해 보자!

 

🔒 1012번 유기농 배추

✔ 문제 설명

🚩 요구사항 분석

• 해당 위치에서 상하좌우 판단
• 가로 N, 세로 M  농장
• 방문기록 필요
• 인접해 있는 배추 파악 -> 배추 흰 지렁이++

 

🔑 문제풀이

입력으로 들어오는 값을 A, B로 farm 배열에 저장

더 이상 인접한 배추가 없다면 count++하여 지렁이의 개수를 추가한다.

방향배열 int x, int y 파라미터 적용

상 좌 하 우 위치 이동 시 n*m배열의 크기보다 작아야 호출

farm [nx][ny] = 1이고 (배추가 있고) visit [nx][ny] = false로 아직 방문하지 않았다면 dfs 메서드를 재귀적으로 호출하여 방문수행

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

public class Main {
    public static int T;
    public static int row;
    public static int col;
    public static int K;

    public static int count;
    public static int[][] farm;
    public static boolean[][] visit;

    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};


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

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

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            col = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            count = 0;

            farm = new int[row][col];
            visit = new boolean[row][col];
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                farm[A][B] = 1;
            }

            for (int j = 0; j < row; j++) {
                for (int k = 0; k < col; k++) {
                    if (farm[j][k] == 1 && !visit[j][k]) {
                        dfs(j, k);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }


    }

    public static void dfs(int x, int y) {

        visit[x][y] = true;

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

            if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
                if (farm[nx][ny] == 1 && !visit[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }
}