[JAVA] 메모리 사용량과 시간을 줄이는 간단한 아이디어

문제는 백준 2573번 문제로 진행했다.

 

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

2573번: 빙산

 

 

1. 문제 풀이

 

1) 2차원 배월의 모든 원소가 0인가? 그렇다면 6)으로 간다. 그게 아니라 하나라도 0보다 큰 수가 있다면 2)번으로간다.

2) answer 를 1증가 시킨다.

3) 2차원 배열을 1년이 지난 배열로 만든다. 

4) bfs를 이용해 영역의 수를 카운트하고 2이상이면 ok에 표시하고 6)번으로 간다.

5) 2)반복한다.

6) ok가 true 라면 answer를 출력하고 아니면 0을 출력한다.

 

 

 

2.  방문체크를 int형 배열이 아니라 boolean 배열로 하자.

방문체크를 하는 변수를 visited라고 한다면 

 

Main 클래스 내에 static으로 선언하고 메모리 측면에서 상당한 이득을 보는 것 같다. 또한 속도도 미묘하게 빨라졌다.

 

 

 

3.  배열의 복사는 최후의 수단으로 하자.

 

배열에 어떤 작업을 하고자 할 때, 하나의 똑같은 배열을 만들어 놓고 로직을 작성하면 매우 쉽겠지만 메모리와 성능면에서 좋지 않다.

 

메모리와 성능을 높이고 싶다면 배열 하나로 작업할 수 있다면 그대로 두고 작업하는 것이 좋다.

 

다시 말하면, 배열 하나를 새로 만들어 놓고 즉 배열 2개로 반복문 1번 돌리는 것과 

 

배열 1개로 반복문 2번 돌리는 것중에 후자가 훨신 성능이 좋다. 

 

 

위 에서 보이는 것 처럼 배열 복사를 없애고 반복문 2번 돌렸는데도 불구하고 메모리와 속도에서 증가 하였다.

 

 

<전체 코드>

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

public class Main{
    static int n,m;
    static int[][] arr;
    static int[][] d4 = new int[][]{{0,-1},{0,1},{1,0},{-1,0}};
    static int answer = 0;
    static boolean[][] visited;

    static public void main(String[] args) throws IOException{
        FastScanner fs =new FastScanner();
        n = fs.nextInt(); m = fs.nextInt();
        arr = fs.read2DArray(n,m);
        boolean ok = false;

        while(checkArr()){
            answer++;
            OneYearsLater();
            if(countArea()>=2){
                ok = true;
                break;
            }
        }
        System.out.printf("%d\n",(ok?answer:0));
        

    }

    private static boolean checkArr(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]>0) return true;
            }
        }
        return false;
    }

    private static void OneYearsLater(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]>0) {
                    int cnt = 0;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + d4[k][0];
                        int ny = j + d4[k][1];
                        if (0 <= nx && nx < n && ny >= 0 && ny < m
                                && arr[nx][ny] == 0) {
                            cnt++;
                        }
                    }
                    arr[i][j] = arr[i][j]-cnt<=0?-1:arr[i][j]-cnt;
                }
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]==-1) arr[i][j]=0;
            }
        }

    }

    private static int countArea(){
        int cnt = 0;
        visited = new boolean[n][m];
        for(int i=0;i<n;i++) visited[i] = new boolean[m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]>0 && visited[i][j]==false){
                    cnt++;

                    Queue<Pos> q = new LinkedList<>();
                    q.offer(new Pos(i,j));
                    visited[i][j]=true;

                    while(!q.isEmpty()){
                        Pos cur = q.poll();

                        for(int k=0;k<4;k++){
                            int nx = cur.x+d4[k][0];
                            int ny = cur.y+d4[k][1];
                            if(nx>=0 && nx<n && ny>=0 && ny<m
                            && arr[nx][ny]>0 && visited[nx][ny]==false){
                                visited[nx][ny]=true;
                                q.offer(new Pos(nx,ny));
                            }
                        }
                    }
                }
            }
        }
        return cnt;
    }


    private static void print2DArray() {
        Arrays.stream(arr).forEach(
                o->{
                    Arrays.stream(o).forEach(System.out::print);
                    System.out.println();
                }

        );
    }

    static class Pos{
        int x,y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static class FastScanner {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public String next() throws IOException{
            while(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException{
            return Integer.parseInt(next());
        }

        public int[][] read2DArray(int n,int m) throws IOException{
            int[][] a = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    a[i][j] = nextInt();
                }
            }
            return a;
        }

    }
}