[BOJ] 1012번: 유기농 배추 (Java)

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

 

문제 설명

이 문제는 배추밭에 필요한 배추흰지렁이의 총 마리수를 구해야한다. 배추가 서로 인접해있는 구역 하나 당 한 마리의 배추흰지렁이가 필요하기에, 배추가 있는 구역의 수를 세어 출력하면 된다.

사진과 같은 배추밭은 배추 구역이 5개, 따라서 답도 5이다.

즉 배추가 심어진 칸(1)이 상하좌우로 붙어있는 면적은 구역이 된다.

 

시도 1 - Comparator로 2차원 배열을 탐색하기

이 코드는 Comparator로 2차원 배열을 탐색하는데, 배추가 있는 구역의 바로 오른쪽/아래가 인접하면 같은 덩어리로 간주하게끔 했다.

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

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

        StringTokenizer field = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(field.nextToken());
        int N = Integer.parseInt(field.nextToken());
        int K = Integer.parseInt(field.nextToken());

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < T; i++) {
            result.append(getCabbagePosition(K)).append("\n");
        }

        System.out.print(result);
    }

    static int getCabbagePosition(int K) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] cabbages = new int[K][2];

        for (int i = 0; i < K; i++) {
            StringTokenizer xOrY = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(xOrY.nextToken());
            int y = Integer.parseInt(xOrY.nextToken());
            int[] arr = {x,y};
            cabbages[i] = arr;
        }

        Arrays.sort(cabbages, (o1, o2) -> {
            if (o1[0] - o2[0] == 0)
                return o1[1] - o2[1];

            else return o1[0] - o2[0];
        });

        return countEarthWorm(cabbages, K);
    }

    static int countEarthWorm(int[][] arr, int K) {
        int count = 0;

        for (int i = 0; i < K; i++) {
            if ((arr[i][0] + 1 == arr[i+1][0] && arr[i][1] == arr[i+1][1])
                || (arr[i][0] == arr[i+1][0] && arr[i][1] + 1 == arr[i+1][1])) {
                continue;
            }

            else {
                count++;
                break;
            }
        }
        return count;
    }
}

 배추가 있는 (x,y) 좌표를 정렬하였을 때 만약 바로 다음 좌표가 오른쪽/아래로 인접하면 같은 덩어리로 간주하려했는데, 그래프 연결은 바로 다음 원소만 인접한다고 생기는 것이 아닐뿐더러 count++의 기준도 이상했다. 따라서 이런 방식으로 구현하기에 복잡도가 올라가 다른 방식을 찾아보려 했다.

 

시도 2 - 배열 내 요소를 오른쪽, 아래 방향으로 탐색하기

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

public class Main2 {
    static int M, N, K, count;
    static int[][] field;

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

        // 밭에 배추 심기
        for (int i = 0; i < T; i++) {
            // 밭 크기, 배추 개수
            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];
            cabbages = new int[K][2];

            // 배추 심은 좌표값 = 1
            for (int j = 0; j < K; j++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st2.nextToken());
                int y = Integer.parseInt(st2.nextToken());
                field[x][y] = 1;

                // 배추 위치 배열에 저장
                cabbages[j][0] = x;
                cabbages[j][1] = y;
            }

            count = 0;
            for (int j = 0; j < K; j++) {
                int x = cabbages[j][0];
                int y = cabbages[j][1];

                if(field[x][y] == 0)
                    continue;

                countEarthWorm(x, y);
            }
            result.append(count).append("\n");
        }

        System.out.println(result);
    }

    public static int countEarthWorm(int x, int y) {
        field[x][y] = 0; // 체크 완료했기에 중복 count 방지를 위해 0으로 변경

        if (x<M || y<N) {
            if (x==M-1 && y==N-1){
                count++;
                return 0;
            }

            if (x==M-1) {
                if ((field[x][y+1] == 0)) {
                    countEarthWorm(x, y+1);
                }
            }

            if (y==N-1) {
                if ((field[x+1][y] == 0)) {
                    countEarthWorm(x+1, y);
                }
            }

            if ((field[x+1][y] == 0) && (field[x][y+1] == 0)) {
                count++;
                return 0;
            }

            else {
                if (field[x+1][y] == 1) {
                    countEarthWorm(x+1, y);
                }

                if (field[x][y+1] == 1) {
                    countEarthWorm(x, y+1);
                }
            }
        }
        return 0;
    }
}

이번에는 Comparator를 버리고, 그냥 좌표를 처음부터 끝까지 탐색하려했다. 하지만 문제는 이 코드에서도 나는 오른쪽, 아래쪽에 바로 인접한 정점만 확인하려 했던 것이다. 배추밭에서의 그래프는 무방향이므로 상하좌우 4방향을 모두 검사해야한다.

또한 인덱스도 field[y][x]로 확인해야했는데 뒤집어서 설정했다는 것도 큰 오류였다.

(* 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50),  배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1))

 

(⭐️최종) 시도 3 - BFS, DFS를 활용하여 탐색하기

위 시도 끝에 내가 고려해야할 점은 2가지였다.

 

1. 현재 정점에서 인접한 상하좌우 4방향을 모두 탐색하기

검사해야할 좌표: 현재 좌표의 상하좌우 1칸 근방에 있는 노드 4개
- 방향: (-1,0), (1,0), (0,-1), (0,1)
⇒ int[] dx = {1,-1, 0, 0} : x좌표 direction
& int[] dy = {0, 0, 1, -1} : y좌표 direction

// 상하좌우 4가지 확인 (0, 1) (0,-1) (1,0) (-1,0)
            for (int dir = 0; dir < 4; dir++) {
                int nextJ = j + dy[dir];
                int nextI = i + dx[dir];
                .
                .
                .​

둘을 조합한 값을 현재 좌표에 더해 이동시키면, 현재 좌표의 상하좌우 1칸 근방에 있는 좌표를 모두 표현 가능하다.

따라서 만약 좌표 값이 1이면(배추가 있으면) 그 노드의 상하좌우를 검사한다.

이를 상하좌우 모든 좌표 값이 모두 0이 나올 때까지 반복하면 된다.

 

 

2. 탐색 기준 정하기

이때까지는 배추가 있는 노드의 오른쪽이나 아래에도 배추가 있다면(값이 1이라면) 순차적으로 탐색을 진행했다. 하지만 이 방식은 배열 요소 값이 1임에도 미처 탐색하지 못하고 지나치게 될 수 있기에 적합하지 않았다.

따라서 적절한 우선 순위나 기준에 따라 2차원 배열을 탐색해야하기에, 그래프 탐색 방식인 DFS 혹은 BFS를 활용할 수 있다.

DFS(깊이 우선 탐색)
- 재귀
- field 2차원 배열
- boolean visited[] 혹은 field 배열에서 방문한 정점의 값은 0으로 대체

BFS(너비 우선 탐색)
- 큐(FIFO): 큐에 해당 정점 넣고, 검사 시 제거
- field 배열
- boolean visited[] 혹은 field 배열에서 방문한 정점의 값은 0으로 대체

 

사실 이 문제와 같이 2차원 배열을 탐색해야하는 유형의 문제는 대체로 BFS/DFS를 활용하여 푼다. 즉 큐에 검사한 요소들을 넣고 빼서 탐색하거나, 재귀(스택)으로 탐색을 반복하면 된다. 처음 해결했을 때는 이 배추밭은 탐색 순서가 정해져있지 않기에 BFS/DFS 즉 너비 우선/깊이 우선 탐색이 무슨 관련이 있는지, 단순히 '큐나 재귀로 푸는 문제' 같기만 했다. '너비나 깊이를 우선으로 탐색 순서를 정하는 게 배추밭에 배추가 있는(값이 1인) 모든 정점을 탐색해내야하는 것은 거리가 느껴져.'가 내 생각이었다.

하지만 이 의문은 그래프의 정의와 연결관계를 생각해보며 해결할 수 있었다.

 

⚠️ 주의할 점

이 문제는 단순히 DFS/BFS 문제가 아니다. 2차원 배열 내 그래프를 어떻게 탐색할 것인지, 즉 큐나 재귀(스택)을 활용해 어떤 방식으로 탐색하느냐에 달려있다.

 

그래프는 정점(Vertex)와 간선(Edge)의 집합으로, 방향이 있든 없든 상관 없다.

그리고 문제의 배추밭은 루트도 방향도 없는 무방향 비연결 그래프이다.

 

따라서 이 문제에서는 마치 DFS/BFS의 본래 의미인 “탐색 순서”, 즉 깊이나 너비를 우선으로 탐색한다는 의의는 퇴색되어 보이고 실제로도 상대적으로 중요하지 않다. 핵심은 배열 내 값이 1인 정점 기준으로, 상하좌우 인접한 1들이 있는지 덩어리로 묶어 탐색(connected component 탐색)한다. 서로 연결된 것만 다 훑는 것이 문제의 목표로, 어느 방향부터 우선적으로 탐색할 것인지 구체적인 순서는 중요하지 않은 특수 케이스다.

 

DFS/BFS는 개념, 탐색 전략이고 큐/재귀(스택)은 구현 도구이다. 여기서는 정점간 연결 관계를 완전히 탐색하기 위한 도구로 DFS/BFS의 구현 도구인 큐/재귀(스택)을 이용할 수 있다. 즉, 단순 DFS/BFS 문제라기 보다는 그래프 연결 관계 탐색이라는 문제 목표를 위해 DFS/BFS를 활용하여 풀 수 있는 것 핵심이다.

특히 내가 처음에 DFS, BFS를 납득하기 어려웠던 이유는 DFS, BFS를 구현할 때 이때까지는 번호가 매겨진 정점이 어떤 정점과 이어져있는지를 확인하여 각 정점별 배열에 넣었기 때문이다. 배열에 들어간 요소들이 너비 우선이나 깊이 우선이라는 기준에 따라 어떤 정점과 이어져있는지 하나씩 검사하는 과정이었다. 그래서 DFS, BFS를 탐색 순서를 찾기 위한 용도로만 이제껏 생각해왔다.

 

그래프 정의에 따르면, 이 배추밭은 루트도 방향도 없기에 '무방향 비연결 그래프'이다. 그래프 탐색 순서라는 개념이 들어간 DFS/BFS는 결국 정점간 연결관계를 모두 완전히 탐색한다는 점에서 탐색 전략이기도 하다.

결국 모든 정점을 탐색하기 위해, 탐색 방식에 있어서 너비나 깊이를 우선으로 탐색할지만 결정한 것에 그치지 않는다. 즉, 이번 문제에서는 DFS/BFS를 구현하는 큐/재귀(스택)으로 모든 연결된 정점을 탐색하겠다는 목표로 DFS/BFS 개념을 활용하면 되는 것이다!

 

BFS - 큐

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

public class Bfs {
    static int[][] field;
    static int M, N, K;
    static int[] dx = {1,-1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

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

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < T; i++) {
            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];

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

            int count = 0;
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < M; x++) {
                    if(field[y][x] == 1) {
                        count++; // 지렁이 필요한 구역 하나씩 count
                        bfs(y,x);
                    }
                }
            }
            result.append(count).append("\n");
        }

        System.out.print(result);
    }

    static void bfs(int y, int x) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        field[y][x] = 0; // 방문
        queue.add(new int[]{y,x});

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int j = cur[0];
            int i = cur[1];

            // 상하좌우 4가지 확인 (0, 1) (0,-1) (1,0) (-1,0)
            for (int dir = 0; dir < 4; dir++) {
                int nextJ = j + dy[dir];
                int nextI = i + dx[dir];
                if (nextI>=0 && nextI<M && nextJ>=0 && nextJ<N && field[nextJ][nextI] == 1) {
                    field[nextJ][nextI] = 0; // 방문 확인
                    queue.add(new int[]{nextJ, nextI});
                }
            }
        }
    }
}

 

DFS - 재귀

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

public class Dfs {
    static int[][] field;
    static int M, N, K;
    static int[] dirX = {1,-1, 0, 0};
    static int[] dirY = {0, 0, 1, -1};

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

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < T; i++) {
            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];

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

            int count = 0;
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < M; x++) {
                    if(field[y][x] == 1) {
                        count++; // 지렁이 필요한 구역 하나씩 count
                        dfs(y,x);
                    }
                }
            }
            result.append(count).append("\n");
        }

        System.out.print(result);
    }

    // 재귀
    static void dfs(int y, int x) {
        field[y][x] = 0; // 방문 확인

        for (int i = 0; i < 4; i++) {
            int nextY = y + dirY[i];
            int nextX = x + dirX[i];

            if (nextY>=0 && nextY<N && nextX>=0 && nextX<M && field[nextY][nextX] == 1) {
                dfs(nextY, nextX);
            }
        }
    }
}

 

배추밭 탐색 시 모든 정점을 확인하되, 값이 1이라면 탐색 시작 시 count++(구역의 개수)을 해준다. 중요한 포인트는, 이때 이 정점은 BFS(큐)나 DFS(재귀)로 상하좌우까지 확인되고 이 정점의 값 1을 0으로 값을 바꿔주어 다음 배추밭 탐색에서 다시 확인(재방문)되어 count가 증가되지 않게 해주어야한다.

---

 

배운 점

이번 문제에서 시도 1, 2가 틀렸던 것은 이 문제의 본질이 그래프 문제임을 몰랐기 때문이라 생각한다. 만약 배추가 있단 좌표를 정렬 하고 그 다음 원소(오른쪽, 아래)만 비교하면 무방향 그래프의 연쇄/분기 연결을 놓칠 것이다. 또한 인덱스가 뒤바뀌거나(field[y][x]), 구역 개수를 세는 count++의 타이밍도 중요 했었다...

 

그래프라는 주제를 깨닫고 나서는 문제 풀이를 완전히 이해할 수 있었다. 결국 2차원 배열은 암묵적 그래프로, 앞으로도 2차원 배열을 탐색할 일이 있으면 그래프 탐색 BFS/DFS 개념을 활용할 수 있다. 이 문제에서는 배추밭을 그래프로 이해하면 격자의 각 칸을 정점, 상하좌우 인접을 간선으로 생각해볼 수 있다.

 

코드를 짜면서 앞서 언급했듯이 그저 큐나 재귀로 푼 문제 같다고만 느꼈다 했는데, 명심할 점은 DFS/BFS는 “어떤 순서로 방문할지”를 정하는 전략이고, 재귀(스택)/큐는 그 전략을 실현하는 구현 수단이다. 여기서는 무방향 그래프이기에 어떤 순서로 방문할지가 주 쟁점이 되기 보다는 모든 정점을 탐색하고자 하는 의도에서 BFS/DFS를 탐색에 활용한다.

 

 

그리고 상하좌우 모두를 검사하기 위해 x,y 방향을 지정해주는 dirX={1,-1,0,0}, dirY={0,0,1,-1} 같은 배열을 좌표에 조합하여 더해 쓸 수 있다는 새로운 아이디어도 얻었다!