글 읽기 - [7569 토마토] javascript 메모리 초과가 나옵니다 ㅠㅠ

engus0927 2년 전 0

2차원 토마토 문제는 문제없이 맞추었는데 3차원 토마토 문제에서는 2%정도에서 메모리 초과 오류가 나네요...

혹시 이유가 짐작가시는 분이 계실까요? ㅠㅠ 도와주시면 정말로 감사드리겠습니다

마음에 걸리는 부분이 있다면

1. BFS에서 Queue를 활용하며 참조한 데이터가 삭제되지 않아서 난건 아닐지? (하지만 Shift를 사용하면 시간초과가 나서 코드의 방법으로 인덱스와 배열 길이를 저장해서 구현하였습니다)

2. 쓸데없이 안사용해도 될 변수가 정의 되었는지?

3. 그래프에 값 저장하는 부분에서 동 서 남 북 위 아래 일일히 체크 하는 코드가 혹시나 잘 못 된것 일지..?(문제가 된다면 시간복잡도에서 문제가 될 것 같은데 메모리 초과와는 관계가 없다고 판단됩니다)

입니다.. 하지만 아무리 생각해도 잘 모르겠네요

이유를 아시는 고수님들 답변 달아주시면 정말 감사드리겠습니다..!!!

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let inputCount = 2;
let row, col, h;
let graph; // 안익은 토마토, 익은 토마토들이 연결되는 그래프를 구현하기 위한 배열
let tomatoBox = []; // 토마토의 위치가 기록되는 배열
let startTomatoArray = []; // 익은 토마토의 좌표들이 들어가는 배열, BFS에 들어감
let periodArray; // BFS를 순회하며 토마토가 익는 날짜를 기록하는 배열
let emptyCount = 0;
let visited; // 방문한 좌표를 다시 방문하지 않기 위한 배열
let count = 0;
let max = 0;

let x = 0;
let y = 0;
let z = 0;

const bfs = (vArr) => {
    let queue = Array.from(vArr);
    let queueLength = 0;
    let idx = 0;
    vArr.forEach(v => {
        periodArray[v.x][v.y][v.z] = 1;
        visited[v.x][v.y][v.z] = true
    })
    queueLength = queue.length
    while(queueLength) {
        let out = queue[idx];
        idx += 1;
        queueLength -= 1;
        graph[out.x][out.y][out.z].forEach( element => {
            if(!visited[element.x][element.y][element.z]) {
                if (periodArray[element.x][element.y][element.z] == 0 || periodArray[element.x][element.y][element.z] > periodArray[out.x][out.y][out.z] + 1) {
                    periodArray[element.x][element.y][element.z] = periodArray[out.x][out.y][out.z] + 1;
                }
                queue.push(element);
                queueLength += 1;
                visited[element.x][element.y][element.z] = true;
            }
        });
    }
}

rl.on('line', (input) => {
    if(inputCount == 2) {
        [col, row, h] = input.split(' ').map(Number);
        graph = Array.from(Array(row), () => Array.from(Array(col), () => Array(h).fill(0)));
        for(let i = 0 ; i < row ; i++) {
            for(let j = 0 ; j < col ; j++){
                for(let k = 0 ; k < h ; k++){
                    graph[i][j][k] = [];
                }
            }
        }
        visited = Array.from(Array(row), () => Array.from(Array(col), () => Array(h).fill(false)));
        periodArray = Array.from(Array(row), () => Array.from(Array(col), () => Array(h).fill(0)));
        tomatoBox = Array.from(Array(row), () => Array.from(Array(col), () => Array(h).fill(-1)));
        inputCount -= 1;
    } else {
        input.split(' ').map(Number).forEach( element => {
            tomatoBox[x][y][z] = element;
            y += 1;
        });
        y = 0;
        x += 1;
        if (x == row) {
            x = 0;
            z += 1;
        }
        if(z == h) {
            rl.close();
        }
    }
    
});

rl.on('close', () => {
    for(let i = 0 ; i < row ; i++) {
        for(let j = 0 ; j < col ; j++){
            for(let k = 0 ; k < h ; k++){
                if(tomatoBox[i][j][k] == 1){
                    startTomatoArray.push({x: i, y: j, z: k});
                }
                if(tomatoBox[i][j][k] == -1){
                    emptyCount += 1;
                }
            }
        }
    }
    for(let i  = 0 ; i < row ; i++) {
        for(let j  = 0 ; j < col ; j++){
            for(let k  = 0 ; k < h ; k++){
                if(tomatoBox[i][j][k] == 1 || tomatoBox[i][j][k] == 0){
                    if (i != 0) {
                        if (tomatoBox[i-1][j][k] == 1 || tomatoBox[i-1][j][k] == 0) {
                            graph[i][j][k].push({x: i-1, y: j, z: k});
                        }
                    }
                    if (i != row-1) {
                        if (tomatoBox[i+1][j][k] == 1 || tomatoBox[i+1][j][k] == 0) {
                            graph[i][j][k].push({x: i+1, y: j, z: k});
                        }
                    }
                    if (j != 0) {
                        if (tomatoBox[i][j-1][k] == 1 || tomatoBox[i][j-1][k] == 0) {
                            graph[i][j][k].push({x: i, y: j-1, z: k});
                        }
                    }
                    if (j != col-1) {
                        if (tomatoBox[i][j+1][k] == 1 || tomatoBox[i][j+1][k] == 0) {
                            graph[i][j][k].push({x: i, y: j+1, z: k});
                        }
                    }
                    if (k != 0) {
                        if (tomatoBox[i][j][k-1] == 1 || tomatoBox[i][j][k-1] == 0) {
                            graph[i][j][k].push({x: i, y: j, z: k-1});
                        }
                    }
                    if (k != h-1) {
                        if (tomatoBox[i][j][k+1] == 1 || tomatoBox[i][j][k+1] == 0) {
                            graph[i][j][k].push({x: i, y: j, z: k+1});
                        }
                    }
                }
            }
        }
    }

    bfs(startTomatoArray);
    
    for(let i = 0 ; i < row ; i++) {
        for(let j = 0 ; j < col ; j++){
            for(let k = 0 ; k < h ; k++){
                if(periodArray[i][j][k] != 0) {
                    count += 1;
                }
                if(max < periodArray[i][j][k]) {
                    max = periodArray[i][j][k];
                }
            }
        }
    }

    if (count != row*col*h - emptyCount) {
        console.log(-1);
    } else {
        console.log(max-1);
    }


    process.exit();
});

nahwasa 2년 전 1

우선 소소하게 periodArray는 없앨 수 있어요. visited에 period까지 같이 기입하면 됩니다. (0이면 아직 방문 안한것, 방문했다면 period 기입)

메모리 터진게 제 생각엔 queue가 아니라 저 graph 때문에 터진 것 같습니다.

const dx = [-1, 1, 0, 0, 0, 0];
const dy = [0, 0, -1, 1, 0, 0];
const dz = [0, 0, 0, 0, -1, 1];

이런식으로 정의해서 그때그때 위치를 찾으면 훨씬 효율적이겠죠.

engus0927 2년 전 1

덕분에 해결했습니다!! 정말로 감사드려요 ㅠㅠ

그래프는 필요가 없는 부분이었네요 알려주셔서 감사드립니다!!

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

문제

문제

출처

ICPC

[7569 토마토] javascript 메모리 초과가 나옵니다 ㅠㅠ

engus0927 2년 전 0

nahwasa 2년 전 1

engus0927 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말