[99클럽 코테 스터디] 32일차 TIL DFS/BFS

 

 

오늘의 문제는 백준

 

6080. Bad Grass

 

 

문제

 

 

 

문제 설명 

목초지의 각 구역의 고도를 측정하여, 고도가 1 이상인 구역들이 서로 인접해 있을 경우 하나의 Bad Grass으로 간주하고, 이러한 섬의 개수를 계산하는 문제입니다. 인접한 구역은 수평, 수직, 대각선으로 연결된 경우를 포함합니다.

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 50분이 걸렸습니다.

 

 

 

문제 접근 방식

BFS를 사용해 Bad Grass의 개수를 계산합니다. 주어진 2차원 배열에서 고도가 1 이상인 구역을 섬으로 간주하고, 인접한 모든 방향으로 연결된 구역들을 탐색하여 하나의 섬으로 묶습니다. 각 섬을 발견할 때마다 BFS를 수행하여 해당 섬에 속하는 모든 구역을 방문 처리하고, 섬의 개수를 증가시킵니다. 이렇게 하여 전체 지도를 탐색하며 섬의 총 개수를 계산합니다. 

 

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    private static int R, C;
    private static int[][] map;

    public static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        map[r][c] = 0; 

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentX = current[0];
            int currentY = current[1];

            for (int[] direction : directions) {
                int newX = currentX + direction[0];
                int newY = currentY + direction[1];

                if (newX >= 0 && newX < R && newY >= 0 && newY < C && map[newX][newY] > 0) {
                    queue.add(new int[]{newX, newY});
                    map[newX][newY] = 0;
                }
            }
        }
    }

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];
        
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int islandCount = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] > 0) { 
                    bfs(i, j);
                    islandCount++;
                }
            }
        }

        System.out.println(islandCount);
    }
}

 

 

BFS 알고리즘 사용하기

고도가 1 이상인 구역을 발견하면, 그 지점을 시작점으로 BFS를 수행합니다. 

1. 큐 초기화 : 발견된 구역의 좌표를 큐에 추가하고, 그 구역을 방문 처리합니다. 다시 말해 고도를 0으로 변경하여 다시 방문하지 않도록 합니다.
2. 탐색 시작 : 큐에서 좌표를 하나씩 꺼내어 그 지점에 상하좌우, 대각선에 있는 구역을 검사합니다. 인접한 구역 중 고도가 1 이상인 구역이 있으면, 그 구역을 큐에 추가하고 방문 처리합니다.
3. 반복 : 큐가 빌 때까지 이 과정을 반복하여 하나의 섬에 속하는 모든 구역을 탐색합니다.
4. 섬 개수 증가 : BFS가 끝나면 하나의 섬에 대한 탐색이 완료된 것이므로 섬의 개수를 증가시킵니다.

 

 

 

메모리 초과 

이 문제에선 입력 크기가 최대 1,000 x 1,000으로 주어지기 때문에 메모리 초과를 방지해야 합니다. BFS로 탐색하면서 각 섬을 방문 처리하는 방식을 사용해 큐의 크기를 관리하고 메모리 사용을 최소화 할 필요가 있습니다. 

1. 맵 크기 고려 : 맵의 크기가 매우 클 경우, 초기 맵을 저장하는 2차원 배열 자체가 많은 메모리를 차지할 수 있습니다. 
2. BFS의 공간 복잡도 : BFS에서 사용하는 큐의 공간 복잡도는 최악의 경우 O(R * C)까지 증가할 수 있습니다. 이 때문에 최적화된 메모리 관리를 통해 BFS가 실행되도록 해야 하며, BFS를 통해 방문한 지점을 즉시 처리하여 메모리 소모를 줄이는 방식으로 접근했습니다.

 

 

 

 

 

 

이렇게 오늘 32일차 TIL을 작성해 보았습니다.