99클럽 코테 스터디 32일차 TIL | Bad Grass

🖥️ 문제

Bessie was munching on tender shoots of grass and, as cows do, contemplating the state of the universe. She noticed that she only enjoys the grass on the wide expanses of pasture whose elevation is at the base level of the farm. Grass from elevations just 1 meter higher is tougher and not so appetizing. The bad grass gets worse as the elevation increases.

Continuing to chew, she realized that this unappetizing food grows the sides of hills that form a set of 'islands' of bad grass among the sea of tender, verdant, delicious, abundant grass.

Bessie donned her lab coat and vowed to determine just how many islands of bad grass her pasture had. She created a map in which she divided the pasture into R (1 < R <= 1,000) rows and C (1 < C <= 1,000) columns of 1 meter x 1 meter squares. She measured the elevation above the base level for each square and rounded it to a non-negative integer. She noted hungrily that the tasty grass all had elevation 0.

She commenced counting the islands. If two squares are neighbors in any of the horizontal, vertical or diagonal directions then they are considered to be part of the same island.

How many islands of bad grass did she count for each of the supplied maps?

📝 풀이

import java.util.*;

public class Main {
    static int R, C;
    static String[][] graph;
    static int[][] d = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        sc.nextLine(); // 줄바꿈 처리

        graph = new String[R][C];
        for (int i = 0; i < R; i++) graph[i] = sc.nextLine().split(" ");

        int cnt = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (graph[i][j].compareTo("0") > 0) {
                    bfs(i, j);
                    cnt++;
                }
        System.out.println(cnt);
    }

    static void bfs(int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { y, x });
        graph[y][x] = "0";

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            for (int[] dir : d) {
                int Y = curr[0] + dir[0], X = curr[1] + dir[1];
                if (Y >= 0 && Y < R && X >= 0 && X < C && graph[Y][X].compareTo("0") > 0) {
                    q.add(new int[] { Y, X });
                    graph[Y][X] = "0";
                }
            }
        }
    }
}

문제는 연결 요소를 세는 문제다. 0이 아닌 부분이 연결된 경우는 섬으로 여기는 것. 문제를 해결하기 위해 BFS(너비 우선 탐색)을 사용했다.

R과 C를 입력받아 격자의 크기를 정하고, 고도를 나타내는 R x C 크기의 2차원 배열 grid를 생성한다. 이후 큐와 배열을 사용하여 8방향 이동했다.