[Java] 백준 1012 : 유기농 배추

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

1.

문제를 처음 읽었을 때, 테스트 케이스 2의 결과가 2라는 것이 이해가 가지 않았다.

문제를 다시 천천히 읽어보고 해석해보니 결국 모여있는 배추 집합의 수를 구하는 문제였다.

전에 풀었던 '백준 2667 : 단지 번호 붙이기' 문제와 유사하다는 것을 알 수 있었다.

(그때는 C언어로 풀었는데 이번에는 Java로 풀어보게 되네.. 확실히 망할 포인터 쓰는 C보다는 Java가 더 편리한 것 같다.)

 

 

2.

BFS 방식을 사용했다. 문제를 풀고 DFS 풀이를 찾아보았는데, 코드가 더 깔끔했고 문제의 $N, M$ 범위가 작아 DFS로 풀어도 시간 초과하지 않는다는 것을 알 수 있었다.

 

문제는 다음과 같은 메커니즘을 택했다.

1. 배열의 모든 원소를 방문하며 1인 원소를 선택

2. 그 원소를 queue에 넣고 queue가 empty가 아닐때 까지 다음을 반복

    2-1. 다음 방문할 $nx, ny$ 를 구하기

    2-2. 그것이 조건에 부합하면 queue에 넣고 해당 원소를 2로 변경한다.

3. queue가 empty가 되면 하나의 배추 집합을 구한 것이니 cnt 증가시킨다.

 

 

3.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][] cabbage;
    static Queue<Pos> q;
    static int n, m;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int testCase = sc.nextInt();
        for (int t = 0; t < testCase; t++) {
            m = sc.nextInt();
            n = sc.nextInt();
            int k = sc.nextInt();

            cabbage = new int[n][m];
            for (int i = 0; i < k; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();

                cabbage[y][x] = 1;
            }

            solve();
        }

        sc.close();
    }

    static void solve() {
        q = new LinkedList<>();
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (cabbage[i][j] == 1) {
                    q.offer(new Pos(i, j));
                    cabbage[i][j] = 2;

                    while (!q.isEmpty()) {
                        Pos temp = q.poll();

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

                            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                                if (cabbage[nx][ny] == 1) {
                                    q.offer(new Pos(nx, ny));
                                    cabbage[nx][ny] = 2;
                                }
                            }
                        }
                    }
                    cnt++;
                }
            }
        }

        System.out.println(cnt);
    }
}

class Pos {
    int x, y;

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

 

4.

DFS 방식은 아래의 블로그를 참고하자.

 

[참고] https://blog.naver.com/tlstjd436/221576263866