58 삐약 : 백준 2583| 영역구하기 [바킹독 문제 풀이|BFS|JAVA]

 

 

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

 

 

package BKD_0x9_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class BOJ_2583 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] squares = new int[N][M];
        int[] dx ={0,1,0,-1};
        int[] dy ={1,0,-1,0};


        ArrayList<Integer> areas = new ArrayList<>();
        Queue<Pair> q = new LinkedList<>();

        while(K-->0){
            String[] input =br.readLine().split(" ");
            int lu_x = Integer.parseInt(input[0]); //left under
            int lu_y = Integer.parseInt(input[1]);
            int ru_x = Integer.parseInt(input[2]); //right up
            int ru_y = Integer.parseInt(input[3]);

            for(int i=lu_x;i<ru_x;i++){
                for(int j=lu_y;j<ru_y;j++){
                    squares[i][j] =1;
                }
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(squares[i][j]==0){
                    q.offer(new Pair(i,j));
                    int area=0;
                    while(!q.isEmpty()){
                        Pair p = q.poll();
                        if(squares[p.x][p.y]==0) area ++;
                        squares[p.x][p.y]=1;

                        for(int k=0;k<4;k++){
                            int nx = p.x +dx[k];
                            int ny = p.y +dy[k];

                            if(nx>=0 && nx<N && ny>=0 && ny<M && squares[nx][ny]==0){
                                q.offer(new Pair(nx,ny));


                            }
                        }
                    }
                    areas.add(area);
                }

            }
        }

        Collections.sort(areas);

        System.out.println(areas.size());
        for(int c : areas) System.out.println(c);
        areas.clear();


    }
    public static class Pair{
        int x;
        int y;

        public Pair(int x, int y){
            this.x = x;
            this.y =y;
        }
    }
}

 

 

돌아가긴 하는데 화끈하게 메모리초과와 함께한다.

 

 

수정

 

package BKD_0x9_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class BOJ_2583 {
    static int M ;
    static int N ;
    static int K ;

    static int[][] squares;
    static int[] dx ={0,1,0,-1};
    static int[] dy ={1,0,-1,0};




    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> areas = new ArrayList<>();


        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());


        squares = new int[N][M];

        while(K-->0){
            String[] input =br.readLine().split(" ");
            int lu_x = Integer.parseInt(input[0]); //left under
            int lu_y = Integer.parseInt(input[1]);
            int ru_x = Integer.parseInt(input[2]); //right up
            int ru_y = Integer.parseInt(input[3]);

            for(int i=lu_x;i<ru_x;i++){
                for(int j=lu_y;j<ru_y;j++){
                    squares[i][j] =1;
                }
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(squares[i][j]==0){
                    int area = bfs(i,j);
                    areas.add(area);
                }

            }
        }
        Collections.sort(areas);
        System.out.println(areas.size());
        for(int c : areas) System.out.println(c);
        areas.clear();
    }

    private static int bfs(int x, int y){
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(x,y));
        squares[x][y]=1;
        int area=1;

        while(!q.isEmpty()){
            Pair p = q.poll();

            for(int k=0;k<4;k++){
                int nx = p.x +dx[k];
                int ny = p.y +dy[k];

                if(nx>=0 && nx<N && ny>=0 && ny<M && squares[nx][ny]==0){
                    squares[nx][ny]=1;
                    q.offer(new Pair(nx,ny));
                    area++;
                }
            }
        }
        return area;
    }
    public static class Pair{
        int x;
        int y;

        public Pair(int x, int y){
            this.x = x;
            this.y =y;
        }
    }
}

 

메모리 차이

 

첫번째 코드 : 메모리 초과

• BFS를 수행할 대 큐를 메인 메소드에서 생성하여 여러 bfs호출에 사용한다.
• 메모리에서 지속적으로 큐가 유지되며, 탐색이 끝날 때 까지 큐의 내용이 계속 변경되나 전체 메모리사용량이 더 안정적일 수 있다고 판단한다.
• 그러나 이는 가비지 컬렉션에 의해 회수되지 않아 필요 이상으로 메모리를 점유할 수 있다.

 

두번째 코드 : 정답

• bfs를 수행하는 동안 필요한 경우에면 큐를 생성한다.
• 함수의 호출이 끝날 때 마다 큐가 비워지고, 해당 큐는 가비지 컬헥션에 의해 회수된다.
  이는 메모리 사용량이 일시적으로 증감하는 패턴을 보일 수 있다. 즉 메모리 사용량을 줄이는데에 도움이 되는 동작 방식이다.
• 전체적으로 메모리 사용량의 변동이 있지만 필요 이상으로 큐를 유지하지 않는다.