[Silver-2] 1012번 | 그래프 순회 | BFS | DFS | 자바(Java)

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

 

 

 

해당 문제는 배추를 보호하기 위한 배추흰지렁이의 수를 구하기 위해, 그래프 순회 알고리즘을 사용하는 문제이다.

이전 단계에서 DFS, BFS 문제를 풀이했었다면, 이 문제도 큰 어려움 없이 문제를 풀 수 있다.

 

import java.util.*;

public class Main {
    // 방향 벡터 (상, 하, 좌, 우)
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();  // 테스트 케이스 개수
        
        for (int tc = 0; tc < t; tc++) {
            int m = sc.nextInt();  // 배추밭의 가로 길이
            int n = sc.nextInt();  // 배추밭의 세로 길이
            int k = sc.nextInt();  // 배추의 개수
            
            int[][] field = new int[n][m];  // 배추밭
            boolean[][] visited = new boolean[n][m];  // 방문 여부
            
            // 배추 위치 입력
            for (int i = 0; i < k; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                field[y][x] = 1;  // (y, x) 위치에 배추 심기
            }
            
            int wormCount = 0;  // 지렁이 개수
            
            // 모든 배추밭 탐색
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (field[i][j] == 1 && !visited[i][j]) {
                        bfs(i, j, field, visited, n, m);  // BFS로 탐색
                        wormCount++;
                    }
                }
            }
            
            System.out.println(wormCount);
        }
        sc.close();
    }
    
    // BFS 탐색
    static void bfs(int x, int y, int[][] field, boolean[][] visited, int n, int m) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && field[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
    
}

 

테스트 케이스 t 개수를 입력받고, 각 테스트 케이스에 대해 배추밭의 크기와 배추 위치를 저장한다.

BFS는 큐를 사용하며 탐색하고 새로운 배추 그룹을 발견할 때마다 worm 수를 증가시킨다.

 

헷갈릴 수 있어 설명을 덧붙이자면

문제에서 주어진 배추 위치는 (X, Y) 좌표로, X는 가로, Y는 세로를 나타낸다.

하지만 2차원 배열 field[n][m]에서 행(row)과 열(column)로 접근할 때, 행은 세로(Y), 열은 가로(X)에 해당하므로

배열의 접근 방식과 좌표의 의미를 맞추기 위해 (Y, X)로 처리하였다.

 

또한, DFS로도 문제를 풀이할 수 있겠다.

static void dfs(int x, int y, int[][] field, boolean[][] visited, int n, int m) {
        visited[x][y] = true;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && field[nx][ny] == 1) {
                dfs(nx, ny, field, visited, n, m);
            }
        }
    }