자바 최적화

토마토 문제를 푸는데, 분명 알고리즘은 맞는 것 같은데 마지막 문제가 Time over가 난다..

그래서 짜잘한 부분을 모두 최적화해보았다.

기존 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {

    static int todo;
    static int[][] tomatoes;
    static int width;
    static int height;
    static Queue<Integer[]> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        width = sc.nextInt();
        height = sc.nextInt();
        tomatoes = new int[height][width];
        for(int i = 0; i<height; i++){
            for(int j = 0; j<width; j++) {
                int status = sc.nextInt();
                tomatoes[i][j] = status;
                if(status == 0) todo++;
                else if(status == 1) queue.add(new Integer[]{i,j});
            }
        }
        System.out.print(bfs());
    }

    public static int bfs(){
        if(todo == 0) return 0;
        int level = 1;
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0; i<len; i++){
                Integer[] point = queue.poll();
                int y = point[0];
                int x = point[1];

                if(y-1 >= 0 && tomatoes[y-1][x] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y-1][x] = 1;
                    queue.add(new Integer[]{y-1, x});
                }
                if(y+1 < height && tomatoes[y+1][x] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y+1][x] = 1;
                    queue.add(new Integer[]{y+1, x});
                }
                if(x-1 >= 0 && tomatoes[y][x-1] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y][x-1] = 1;
                    queue.add(new Integer[]{y, x-1});
                }
                if(x+1 < width && tomatoes[y][x+1] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y][x+1] = 1;
                    queue.add(new Integer[]{y, x+1});
                }
            }
            level++;
        }
        return -1;
    }
}

수정 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {

    /**
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
     */
    static int todo;
    static int[][] tomatoes;
    static int width;
    static int height;
    static Deque<int[]> queue = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        width = Integer.parseInt(input[0]);
        height = Integer.parseInt(input[1]);
        tomatoes = new int[height][width];

        for(int i = 0; i<height; i++){
            input = br.readLine().split(" ");
            for(int j = 0; j<width; j++) {
                int status = Integer.parseInt(input[j]);
                tomatoes[i][j] = status;
                if(status == 0) todo++;
                else if(status == 1) queue.add(new int[]{i,j});
            }
        }
        System.out.print(bfs());
    }

    public static int bfs(){
        if(todo == 0) return 0;
        int level = 1;
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0; i<len; i++){
                int[] point = queue.poll();
                int y = point[0];
                int x = point[1];

                if(y-1 >= 0 && tomatoes[y-1][x] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y-1][x] = 1;
                    queue.add(new int[]{y-1, x});
                }
                if(y+1 < height && tomatoes[y+1][x] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y+1][x] = 1;
                    queue.add(new int[]{y+1, x});
                }
                if(x-1 >= 0 && tomatoes[y][x-1] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y][x-1] = 1;
                    queue.add(new int[]{y, x-1});
                }
                if(x+1 < width && tomatoes[y][x+1] == 0){
                    todo--;
                    if(todo==0) return level;
                    tomatoes[y][x+1] = 1;
                    queue.add(new int[]{y, x+1});
                }
            }
            level++;
        }
        return -1;
    }
}

변경점

1. Integer[] -> int[]로 변환
   객체는 메모리 할당과 해제, 그리고 가비지 컬렉션과 관련된 오버헤드가 있다. 따라서 가능하면 원시 자료형을 사용하는 것이 성능에 유리하다.

2. Scanner -> BufferedReader
   Scanner는 여러 번 사용자의 입력을 받지만 BufferedReader는 덩어리 데이터를 한 번에 받는다.

3. LinkedList -> DequeArray
   그냥 해봤는데 Deque를 사용하는게 항상 빠르게 나온다.. 둘이 시간복잡도는 같은데 내부적으로 조금 더 최적화되어있는건가.. ?

   내부적인 메모리 관리 방식과 관련이 있다고 한다. LinkedList는 각 노드마다 메모리 주소를 유지해야 하므로 추가적인 메모리 오버헤드가 발생할 수 있는데 ArrayDeque는 연속적인 메모리 공간에 데이터를 저장하기 때문에 이러한 오버헤드가 적다고 한다.. 급하게 주워들은 얘기이므로 나중에 다시 알아봐야겠다.