[백준] 1012-유기농 배추 (Java)

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

 

문제

 

구현 방식

육지(1)로 표시된 지점들을 탐색하면서 연결된 육지를 올바르게 판단하는 것이 관건인 문제이다.
방문하지 않은 칸을 방문할 때마다, 연결된 모든 칸을 한 번에 탐색하여 육지로 묶는 방식으로 문제를 접근하였다.

 

BFS를 위한 자료구조

• 2차원 배열 check로 방문 여부를 관리한다.
• 큐(Queue)를 활용하여 BFS를 구현한다.
• 이동 방향을 나타내기 위한 dy, dx 배열(상하좌우)을 준비한다.

로직

1. 이중 for문을 통해 모든 좌표들을 하나씩 순회하면서 탐색한다.
2. 아직 방문하지 않은 칸을 발견하면, 해당 칸에서 시작하는 새 육지를 찾은 것이므로, 육지 개수를 담당하는 변수의 값을 1 증가시킨다.
3. 현재 좌표 (y, x)를 큐에 넣고, check[y][x] = 1로 방문 여부를 표시한다.
4. 큐가 빌 때까지 다음 과정을 반복한다.
   • 큐에서 현재 좌표 (y, x)를 꺼낸다.
   • 상하좌우 방향으로 이동할 다음 좌표 (ny, nx)를 구한다.
   • 오버플로우/언더플로우(배열 범위를 벗어남)와 육지 여부, 방문 여부(check[ny][nx])를 확인한다.
   • 조건을 하나라도 충족하면 continue 구문을 통해 방문하지 않는다.
   • 해당 조건들을 불충족 시, 방문하지 않은 육지이므로 check[ny][nx] = 1로 표시 후, 큐에 (ny, nx)를 삽입하여 해당 좌표 주변의 좌표들을 탐색하도록 한다.

 

BFS보다 DFS가 유리한 이유

최단 경로(거리 계산)가 필요하지 않으며, 단순히 연결된 좌표들만 파악하기에 DFS가 이론적으로 더 유리하다.

이유는 즉슨 DFS는 한 경로를 끝까지 파고드는 방식으로 진행되기 때문이다. 연결되어 있는 좌표를 '재귀 호출' 혹은 '스택'을 통해 계속 파고들기 때문에, 단순히 연결된 좌표들만 모두 방문해야 하는 상황에서는 코드가 비교적 간단해질 수 있다.

 

DFS 로직

• 방문 배열 초기화 : 새로운 테스트 케이스(처음 방문하는 육지)마다 check 배열 등을 초기화해주어야 한다.
• DFS 함수 호출 :
  • 방문하지 않은 육지을 찾으면 dfs(y, x) 메서드를 호출한다.
  • DFS 내부에서 상하좌우를 확인하며, 조건에 맞으면 dfs(y, x) 메서드를 재귀 호출한다.

 

정답(BFS)

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

public class Main {

    static Queue<Point> queue = new LinkedList<>();

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

    static StringBuilder sb = new StringBuilder();

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

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            boolean[][] arr = new boolean[m][n];
            boolean[][] check = new boolean[m][n];


            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());

                int tmpY = Integer.parseInt(st.nextToken());
                int tmpX = Integer.parseInt(st.nextToken());
                arr[tmpY][tmpX] = true;
            }

            int cnt = 0;
            int ny = 0, nx = 0, y = 0, x = 0;

            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (arr[j][l]) {
                        if (!check[j][l]){
                            cnt++;

														check[j][l] = true;

		                        queue.offer(new Point(j, l));
                        }
                        
                    }

                    while (!queue.isEmpty()) {
                        Point p = queue.poll();
                        y = p.x;
                        x = p.y;

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

                            if (ny < 0 || ny >= n || nx < 0 || nx >= m || !arr[ny][nx]) {
                                continue;
                            }
                            if (check[ny][nx]) {
                                continue;
                            }

                            check[ny][nx] = true;
                            queue.offer(new Point(ny, nx));
                        }
                    }
                }
            }

            System.out.println(cnt);
        }
    }

}

 

정답(DFS)

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

public class Main {

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static boolean[][] arr, check;
    static int ny, nx, y, x, cnt, m, n;


    static StringBuilder sb = new StringBuilder();

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

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            arr = new boolean[m][n];
            check = new boolean[m][n];


            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());

                int tmpY = Integer.parseInt(st.nextToken());
                int tmpX = Integer.parseInt(st.nextToken());
                arr[tmpY][tmpX] = true;
            }

            cnt = 0;

            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (arr[j][l]) {
                        if (!check[j][l]){
                            cnt++;
                            dfs(j, l);
                        }
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int j, int l) {
        check[j][l] = true;
        for (int i = 0; i < 4; i++) {
            ny = j + dy[i];
            nx = l + dx[i];

            if (ny < 0 || ny >= m || nx < 0 || nx >= n) {
                continue;
            }
            if (!check[ny][nx] && arr[ny][nx]) {
                dfs(ny, nx);
            }
        }

    }

}