[백준_JAVA_알고리즘] 1012 유기농 배추 #DFS

다음 문제는 DFS를 활용해서 해결할 수 있습니다.

 

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

public class Main {
    /*
        1. 배추가 나오면 벌레++;
        2. 네 방향 모두 탐색하여, 배추와 인접한 배추 찾기 -> 1을 0으로 변환
        3. 벌레 개수 반환
    */
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int M;
    static int N;
    static int K;
    static int worm;

    // dfs
    public static void dfs(int y, int x){
        visited[y][x] = true;

        // 상하좌우 네 방향 탐색
        for(int i = 0; i < 4; i++){
            int ny = dy[i] + y;
            int nx = dx[i] + x;

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

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

        for(int i = 0; i < T; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            M = Integer.parseInt(stringTokenizer.nextToken());
            N = Integer.parseInt(stringTokenizer.nextToken());
            K = Integer.parseInt(stringTokenizer.nextToken());
            field = new int[N][M];
            visited = new boolean[N][M];
            worm = 0;

            // 배추 심기
            for (int j = 0; j < K; j++) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                int X = Integer.parseInt(stringTokenizer.nextToken());
                int Y = Integer.parseInt(stringTokenizer.nextToken());
                field[Y][X] = 1;
            }

            // 필드 탐색
            for (int k = 0; k < N; k++) {
                for (int l = 0; l < M; l++) {
                    if (field[k][l] == 1 && !visited[k][l]) {
                        dfs(k, l);
                        worm++;
                    }
                }
            }
            System.out.println(worm);
        }
    }
}

field[][]는 배추밭을 나타내는 2차원 배열입니다.

visited[][]는 해당 위치 방문 여부를 체크하는 배열입니다.

dx[], dy[]는 상하좌우 이동을 위한 방향 배열입니다.

M, N은 배추밭의 가로, 세로 크기이고 K는 배추가 심어진 위치의 개수입니다.

 

먼저, K개의 배추 위치를 입력받아 field 배열에 1로 표시합니다.

그 다음, 전체 배추밭을 순회하면서 배추가 있고, 아직 방문하지 않은 위치에 지렁이 수를 1씩 증가시킵니다.

 

x, y 좌표가 반대로 입력되는 이유는 다음과 같습니다.

field = new int[N][M];  // N이 행(y축), M이 열(x축)
field[Y][X] = 1;        // 배추 위치 저장시 Y,X 순서

2차원 배열은 [행][열] 순서로 접근합니다. 따라서 행은 y좌표, 열은 x좌표에 대응합니다.

입력은 (x, y) 좌표평면 형식으로 주어지나, 배열은 [y][x] 형식으로 접근해야 합니다.

 

dfs 메서드의 재귀적 탐색을 통해 해결할 수 있습니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

https://www.acmicpc.net/problem/1012