[백준] 유기농 배추 자바 BFS 풀이(메모리 초과 나는 이유)

문제요약)

- 땅에 배추가 심어져 있는 곳 1, 아닌 곳 0으로 주어짐

- 각 분리된 땅의 개수 세기

 

주의점)

- BFS로 풀 때 메모리 초과 주의

 

풀이)

BFS로 풀어본다면 방문 배추가 심어져있고 방문 안했다면 방문해서 채워나가는 식으로 진행할 수 있습니다.

BFS가 한번 돌고 count를 더해주면 끝입니다.

 

BFS 코드의 일부분인데 위에 주석처리를 해놓은 것처럼 q에 이미 넣은걸 빼면서 방문처리하게되면 다음껄 q에 넣는 동시에 방문처리 하는 것과 비슷해보이지만 해당 케이스가 많아진다면 q에 들어가는 양이 많아지기 때문에 메모리 초과가 발생할 수 있습니다.

 

실제로 해당 문제에서 bfs로 풀면서 주석친 부분에서만 방문처리를 하게된다면 메모리 초과가 뜨게 되기 때문에 bfs문제를 만나면 방문처리를 q에 넣으면서 동시에 해주시면 되겠습니다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Cabbage1012_bfs_blog {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int t, n, m;
    static boolean[][] map;
    static boolean[][] visit;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 테스트 개수, 세로, 가로, 총 지문 개수
        t = sc.nextInt();

        while (--t >= 0) {
            // 땅 만들기
            n = sc.nextInt();
            m = sc.nextInt();
            map = new boolean[n][m];
            visit = new boolean[n][m];

            int a = sc.nextInt();
            for (int i=0; i<a; i++) {
                map[sc.nextInt()][sc.nextInt()] = true;
            }

            int answer = 0;
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (!visit[i][j] && map[i][j]) {
                        visit[i][j] = true;
                        BFS(i, j);
                        answer++;
                    }
                }
            }

            System.out.println(answer);
        }

    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y});

        while(!q.isEmpty()) {
            int[] currentNode = q.poll();
//            visit[currentNode[0]][currentNode[1]] = true; // 여기서 하면 이미 중복된걸 많이 넣기 때문에 메모리 초과

            for (int k=0; k<4; k++) {
                int nx = currentNode[0] + dx[k];
                int ny = currentNode[1] + dy[k];

                if (nx >= n || ny >= m || nx < 0 || ny < 0) continue;
                if (visit[nx][ny] || !map[nx][ny]) continue;
                visit[nx][ny] = true;
                q.offer(new int[] {nx, ny});
            }
        }
    }

}