글 읽기 - 메모리 초과가 나는데 필요한 것만 사용했던 것 같은데 어디 부분을 줄어야 할까요

ehdals8965 5년 전 0

방향이 4방향이기 때문에 현재 방향과 이 객체의 상황까지 오는데 걸린 Count를 저장한다음 for문으로 4방향을 돌려서 각 방향별로 더해야할 Count를 구해서 각각 돌려주고 방향과 현재 가야할 방향이 같다면 1,2,3칸씩 각각 전진하게 하여 Count를 1씩 더해준 다음 Queue에 넣는식으로 하여 문제를 진행하였습니다.. 문제에 대한 답은 구한 것 같은데 메모리 초과가 나는데 어느 부분에서 줄여야 될까요...? Element 객체에 Count를 사용한게 문제일까요...? 나머지 visited[][], map[][] 등은 전부 사용해야할 것 같은데.. 도움 좀 부탁드립니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class main {
    int width;
    int height;
    int[][] map;
    int[][] moveDirEast = {{0, 1}, {0, 2}, {0, 3}};
    int[][] moveDirWest = {{0, -1}, {0, -2}, {0, -3}};
    int[][] moveDirSouth = {{1, 0}, {2, 0}, {3, 0}};
    int[][] moveDirNorth = {{-1, 0}, {-2, 0}, {-3, 0}};

    public main(int width, int height, int[][] map) {
        this.width = width;
        this.height = height;
        this.map = map;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int height = Integer.parseInt(input[0]);
        int width = Integer.parseInt(input[1]);
        int[][] map = new int[height+1][width+1];

        for(int i = 1; i <= height; i++) {
            input = br.readLine().split(" ");
            for(int j = 1; j <= width; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
            }
        }

        int startX, startY, startDir, finishX, finishY, finishDir;

        input = br.readLine().split(" ");
        startY = Integer.parseInt(input[0]);
        startX = Integer.parseInt(input[1]);
        startDir = Integer.parseInt(input[2]);

        input = br.readLine().split(" ");
        finishY = Integer.parseInt(input[0]);
        finishX = Integer.parseInt(input[1]);
        finishDir = Integer.parseInt(input[2]);

        main main = new main(width, height, map);
        System.out.println(main.searchBFS(startX, startY, startDir, finishX, finishY, finishDir));
    }

    int searchBFS(int startX, int startY, int startDir, int finishX, int finishY, int finishDir) {
        boolean[][] visited = new boolean[height + 1][width + 1];
        LinkedList<Element> queueElement = new LinkedList<>();
        queueElement.add(new Element(startX, startY, startDir, 0));
        visited[startY][startX] = true;

        Element temp, dest;
        int currentDir;
        int currentCount;

        while (!queueElement.isEmpty()) {
            temp = queueElement.remove(0);
            currentDir = temp.dir;
            currentCount = temp.count;

            if(temp.x == finishX && temp.y == finishY && temp.dir == finishDir) return temp.count;

            for (int i = 1; i <= 4; i++) {                                                           // 방향 설정
                if (temp.dir == i && isGoRoad(temp.x, temp.y, temp.dir)) {
                    for (int j = 0; j < 3; j++) {
                        dest = searchPoint(temp.x, temp.y, temp.dir, j, temp.count);
                        if (dest.x >= 1 && dest.x <= width && dest.y >= 1 && dest.y <= height &&
                                !visited[dest.y][dest.x] && map[dest.y][dest.x] == 0) {
                            visited[dest.y][dest.x] = true;
                            queueElement.add(dest);
                        }
                    }
                } else {
                    queueElement.add(new Element(temp.x, temp.y, i, currentCount + moveSearch(currentDir, i)));
                }
            }
        }
        return 0;
    }

    boolean isGoRoad(int x, int y, int dir) {
        if(dir == 1) {
            return x+1 <= width && map[y][x+1] == 0;
        } else if(dir ==2) {
            return x-1 >= 1 && map[y][x-1] == 0;
        } else if(dir == 3) {
            return y+1 <= height && map[y+1][x] == 0;
        } else {
            return y-1 >= 1 && map[y-1][x] == 0;
        }
    }

    int moveSearch(int currentDir, int fuctureDir) {
        if(currentDir == 1) {
            if(fuctureDir == 2) return 2;
            else return 1;
        } else if(currentDir == 2) {
            if(fuctureDir == 1) return 2;
            else return 1;
        } else if(currentDir == 3) {
            if(fuctureDir == 4) return 2;
            else return 1;
        } else {
            if(fuctureDir == 3) return 2;
            else return 1;
        }
    }


    Element searchPoint(int x, int y, int dir, int distance, int count) {
        int destX, destY;
        if(dir == 1) {
            destX = x + moveDirEast[distance][1];
            destY = y + moveDirEast[distance][0];
        } else if(dir == 2) {
            destX = x + moveDirWest[distance][1];
            destY = y + moveDirWest[distance][0];
        } else if(dir == 3) {
            destX = x + moveDirSouth[distance][1];
            destY = y + moveDirSouth[distance][0];
        } else {
            destX = x + moveDirNorth[distance][1];
            destY = y + moveDirNorth[distance][0];
        }
        return new Element(destX, destY, dir, count+1);
    }

    class Element {
        int x, y, dir, count;

        public Element(int x, int y, int dir, int count) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.count = count;
        }
    }
}

seico75 5년 전 0

ideone 에서는 아래 경우가 time limit 이 나오는데,

경우에 따라서는 memory 문제가 나올 것 같습니다.

막다른 골목에서가 문제인 것 같습니다. 70 라인..

5 6
0 0 0 0 0 0
0 1 1 1 1 1
0 1 0 1 0 0
0 0 0 1 1 0
0 1 0 0 0 0
1 1 1
3 5 3

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

문제

문제

출처

ICPC

메모리 초과가 나는데 필요한 것만 사용했던 것 같은데 어디 부분을 줄어야 할까요

ehdals8965 5년 전 0

seico75 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말