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

# 오늘의 학습 키워드 

깊이/너비 우선 탐색(DFS/BFS)

 

# 오늘의 문제 

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

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.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

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

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

        R = scanner.nextInt();
        C = scanner.nextInt();
        graph = new int[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        int cnt = 0; // 섬의 개수
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (graph[i][j] > 0) { // 현재 위치가 나쁜 풀일 경우
                    bfs(i, j); // BFS 실행
                    cnt++; // 섬의 개수 증가
                }
            }
        }

    }

    public static void bfs(int y, int x) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{y, x});
        graph[y][x] = 0; // 방문했음을 표시

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int cy = current[0];
            int cx = current[1];

            for (int[] direction : DIRECTIONS) {
                int Y = cy + direction[0];
                int X = cx + direction[1];

                if (Y >= 0 && Y < R && X >= 0 && X < C && graph[Y][X] > 0) {
                    q.add(new int[]{Y, X});
                    graph[Y][X] = 0; // 방문했음을 표시
                }
            }
        }
    }
}

 

# 오늘의 회고 

아... 자꾸 메모리초과뜬다. 야근한다고 게더타운 문제풀이 제대로 못들었는데ㅜㅜ 왜 그런지 확인해봐야할듯