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

 

 

 

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

 

 

문제 접근

 

누가 봐도 이 문제는 그래프이론을 활용한 문제이다.

 

탐색을 통해서 배추흰지렁이를 알아내는 문제라고 생각했기에 BFS와 DFS를 사용하여 풀어가는 문제이다.

 

나는 이번 문제는 DFS를 이용해서 풀어보았다.

 

물론 BFS도 시도하는게 공부에 정석이라고 생각하지만 차라히 다른 문제를 BFS로 접근해서 풀어보는게 성취감에 더 좋을거 같다.

 

DFS 

 

map에서 1인 위치는 배추가 심어진 곳.

 

연결된 1(배추) 영역은 한 마리의 벌레가 방어하면 되므로,

 

아직 방문하지 않은 1의 위치에서 DFS 시작할 때마다 벌레 수(count)를 1 증가.

 

DFS는 재귀를 이용해 상하좌우 인접한 배추(1)들을 탐색하며 visit을 통해 중복 방지.

 

 

dfs(x, y)는 현재 배추 위치 (x, y)에서 시작하여 상하좌우로 연결된 모든 배추를 방문.

 

방문한 배추는 visited[y][x] = true로 체크하여 다시 방문하지 못하게 함.

 

전체 밭을 돌면서 방문하지 않은 배추(=새로운 덩어리)를 발견하면 dfs를 호출하고 벌레 수를 1 증가

 

 

 

import java.io.*;
import java.util.*;

public class Main {
    static int width, height, count;
    static int[][] field;
    static boolean[][] visited;

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

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

        for (int t = 0; t < testCount; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            width = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            count = Integer.parseInt(st.nextToken());

            field = new int[height][width];
            visited = new boolean[height][width];

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

            int wormCount = 0;

            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    if (field[y][x] == 1 && !visited[y][x]) {
                        dfs(x, y);
                        wormCount++;
                    }
                }
            }

            result.append(wormCount).append('\n');
        }

        System.out.print(result);
    }

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

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

            if (isInRange(nx, ny) && !visited[ny][nx] && field[ny][nx] == 1) {
                dfs(nx, ny);
            }
        }
    }

    private static boolean isInRange(int x, int y) {
        return x >= 0 && y >= 0 && x < width && y < height;
    }
}

 

 

아무래도 그래프 이론 공부는 좀 해둬서 그런지 알고리즘면에서는 크게 어려웠던 점은 없었던거 같다.

 

다만 코딩면에서 나는 파이썬을 주로 하면서 성장했기 때문에 자바를 짜는 코드적인 부분에서는 많이 힘들었다.

 

더 성장하도록 열심히 해야겠다.