글 읽기 - 얼음을 기준으로 넣을땐 왜 메모리초과가 나올까요?

gkdud583 2년 전 0

물을 기준으로 리스트에 넣고 얼음을 녹일땐 맞았다고 나오는데

얼음을 기준으로 리스트에 넣을땐 메모리초과가 나옵니다.

어느부분 때문에 메모리초과가 나오는건가요?

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

class Location{
    int y;
    int x;
    Location(int y, int x){
        this.y = y;
        this.x = x;

    }
}

class Main
{
    static final int dy[] = {-1,1,0,0};
    static final int dx[] = {0,0,-1,1};
    static Queue<Location> queue = new LinkedList<>();
    static boolean blockedRoadArr[][];
    static boolean check[][];
    static Queue<Location> glacierList = new LinkedList<>();
    static Location swan2;

    static int tempMap[][];
    static int map[][];

    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        String input[] = sc.nextLine().split(" ");
        int R = Integer.parseInt(input[0]);
        int C = Integer.parseInt(input[1]);

        tempMap = new int[R][C];
        map = new int[R][C];
        blockedRoadArr = new boolean[R][C];
        check = new boolean[R][C];

        ArrayList<Location> swanList = new ArrayList<>();
        for(int i=0; i<R; i++){
            input = sc.nextLine().split("");
            for(int j=0; j<C; j++){
                if(input[j].equals(".")){
                    map[i][j] = 0;
                }else if(input[j].equals("L")){
                    map[i][j] = 2;
                    swanList.add(new Location(i,j));
                }else{
                    map[i][j] = 1;
                    glacierList.add(new Location(i,j));
                }
            }
        }
        Location swan1 = swanList.get(0);
        swan2 = swanList.get(1);

        queue.add(new Location(swan1.y, swan1.x));

        check[swan1.y][swan1.x] = true;

        if(isPossible(R,C)){
            System.out.println(0);
        }else{
            System.out.println(solve(R,C));
        }

    }
    static boolean isPossible(int R, int C){



        while(!queue.isEmpty()){
            Location cur = queue.poll();

            for(int i=0; i<4; i++){
                int y = cur.y + dy[i];
                int x = cur.x + dx[i];

                if(outOfArray(y, x, R, C) || check[y][x])
                    continue;
            
                
                if(y == swan2.y && x == swan2.x){
                    return true;
                }

                check[y][x] = true;
                
                if(map[y][x] == 1){
                    blockedRoadArr[y][x] = true;
                    continue;
                }


                
                queue.add(new Location(y,x));


            }

        }
        return false;
    }
    static boolean outOfArray(int y, int x, int R, int C){
        if(y < 0 || x < 0 || y >= R || x >= C)
            return true;
        return false;
    }
    static int solve(int R, int C){
        for(int i=1;; i++){
            meltGlacier(R, C);
            if(isPossible(R,C))
                return i;
        }

    }
    
    static void meltGlacier(int R, int C){
        copyMap(R,C,map,tempMap);
        for(int i=0, size=glacierList.size(); i<size; i++){
            Location g = glacierList.poll();
            boolean meltable = false;
            for(int j=0; j<4; j++){
                int y = g.y + dy[j];
                int x = g.x + dx[j];

                if(outOfArray(y,x,R,C) || map[y][x] == 1)
                    continue;

                meltable = true;
                tempMap[g.y][g.x] = 0;

                if(blockedRoadArr[g.y][g.x]){
                    blockedRoadArr[g.y][g.x] = false;
                    queue.add(new Location(g.y,g.x));
                }
                break;
                   
                
            }
            if(!meltable){
                glacierList.add(new Location(g.y, g.x));
            }

        }
        copyMap(R,C,tempMap,map);
    }
    static void copyMap(int R, int C, int source[][], int dest[][]){

        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                dest[i][j] = source[i][j];
            }
        }
    }
    
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

얼음을 기준으로 넣을땐 왜 메모리초과가 나올까요?

gkdud583 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말