백준 7569번 토마토 [ Java ]

7569번: 토마토

지금까지 ArrayList를 사용하면 무조건 빠르다고 생각했는데 아니였습니다.

ArrayList의 0번째 원소를 지우는 연산은 뒤에 있는 원소를 전부 한 칸씩 당겨와야하기 때문에 원소의 수에 비례하는 시간이 됩니다. 

글 읽기 - 자바 시간초과가 나는데... 코드 어떻게 손대야할지 모르겠네요...

 

 

자료구조: Linked List 대 ArrayList

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dx = new int[]{1, 0, 0, -1, 0, 0};
        int[] dy = new int[]{0, 1, 0, 0, -1, 0};
        int[] dz = new int[]{0, 0, 1, 0, 0, -1};

        int[] in = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int M = in[0];
        int N = in[1];
        int H = in[2];

        int[][][] cube = new int[H][N][M];
        int[][][] dist = new int[H][N][M];
        Queue<int[]> Q = new LinkedList<>();
        for (int i=0; i<H; i++)
            for (int j=0; j<N; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int k = 0; k < M; k++) {
                    dist[i][j][k] = -1;
                    cube[i][j][k] = Integer.parseInt(st.nextToken());
                    if (cube[i][j][k] == 1) {
                        dist[i][j][k] = 0;
                        Q.add(new int[]{i, j, k});
                    }
                    if (cube[i][j][k] == -1)
                        dist[i][j][k] = -2;
                }
            }
        int max = 0;
        while(!Q.isEmpty()){
            int[] cur = Q.poll();
            for (int dir=0; dir<6; dir++){
                int nx = cur[2] + dx[dir];
                int ny = cur[1] + dy[dir];
                int nz = cur[0] + dz[dir];
                if (nx<0 || nx>=M || ny<0 || ny>=N || nz<0 || nz>=H) continue;
                if (dist[nz][ny][nx]>=0 || cube[nz][ny][nx]==-1) continue;
                dist[nz][ny][nx] = dist[cur[0]][cur[1]][cur[2]] + 1;
                max = Math.max(max, dist[nz][ny][nx]);
                Q.add(new int[]{nz, ny, nx});
            }
        }


        for (int i=0; i<H; i++)
            for (int j=0; j<N; j++)
                for (int k=0; k<M; k++){
                    if (dist[i][j][k]==-1){
                        System.out.print(-1);
                        System.exit(0);
                    }
                }
        System.out.print(max);
    }
}