글 읽기 - [node.js] 자바스크립트 고수들 이거 좀 봐주세요

qorgkr26 3년 전 0

2%에서 자꾸 틀리는 거 보면 큰 값 처리에서 틀리는 거 같은데

아니 솔직히 틀리는 이유를 모르겠음...예외 처리 다 해준 것 같은데

자바스크립트 고수님들의 신랄한 지적 부탁드립니다. 제발 봐줘요..

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let N = +input[0].split(' ')[1];
let M = +input[0].split(' ')[0];

class Tomato{
    constructor(data){
        this.data = data;
        this.parent = null;
        this.isInQueue = false;
        this.distance = 0;
    }
    setParent(i,j){
        this.parent = [i,j];
    }

    setDistance(nodes){
        this.distance = nodes[this.parent[0]][this.parent[1]].distance + 1;
    }

    getParentDis(nodes){
        return nodes[this.parent[0]][this.parent[1]].distance;
    }

}
//일단 시작부터 다 익은 토마토의 위치를 파악한다.
let box = new Array(N);
let points = [];
let tomatos = Array.from(Array(N), () => new Array(M));
for(let i = 0; i < N; i++){
    box[i] = input[i+1].split(' ').map(x => +x);
    for(let j = 0; j < M; j++){
        if(box[i][j] === 1){
            points.push([i,j]);
            tomatos[i][j] = new Tomato(1);
        }else if(box[i][j] === 0){
            tomatos[i][j] = new Tomato(0);
        }else{
            tomatos[i][j] = new Tomato(-1);
        }
    }
}

let check = () => {
    for(let i = 0; i < N; i++){
        for(let j = 0; j < M; j++){
            if(tomatos[i][j].data === 0){return false;}
        }
    }
    return true;
}

let empty = () => {
    let count = 0; 
    for(let i = 0; i < N; i++){
        for(let j = 0; j < M; j++){
            if(tomatos[i][j].data === -1){count++;}
        }
    }
    return count;
}


let dx = [0,0,-1,1];
let dy = [-1,1,0,0];

if(points.length === N * M || empty() === N * M){console.log(0);}
else{
    //모든 토마토가 익기 위한 일수를 센다.
    let visited = Array.from(Array(N), () => new Array(M).fill(false));
    let bfs = (queue) => {
        let start = queue.pop();
        let row = start[0], col = start[1];
        visited[row][col] = true;
        tomatos[row][col].data = 1;
        tomatos[row][col].setParent(row,col);
        //child 찾기
        for(let i = 0; i < 4; i++){
            if(row+dx[i] >= 0 && row+dx[i] <= N-1 && col+dy[i] >= 0 && col+dy[i] <= M-1 ){
                if(box[row+dx[i]][col+dy[i]] === 0 && !tomatos[row+dx[i]][col+dy[i]].isInQueue && !visited[row+dx[i]][col+dy[i]]){
                   queue = [[row+dx[i],col+dy[i]],...queue];
                   tomatos[row+dx[i]][col+dy[i]].isInQueue = true;
                   tomatos[row+dx[i]][col+dy[i]].setParent(row,col);
                   tomatos[row+dx[i]][col+dy[i]].setDistance(tomatos);
                }else if(tomatos[row+dx[i]][col+dy[i]].isInQueue || visited[row+dx[i]][col+dy[i]]){
                    if(tomatos[row+dx[i]][col+dy[i]].getParentDis(tomatos) > tomatos[row][col].distance){
                        tomatos[row+dx[i]][col+dy[i]].setParent(row,col);
                        tomatos[row+dx[i]][col+dy[i]].setDistance(tomatos);
                    }
                }
            }
            }
            return queue;
        }
        let result = [];
        for(let i=0; i<points.length; i++){
            result.push(bfs([points[i]]));
        }
        while(result.filter(r => r.length > 0).length > 0){
            result.forEach((r,idx) => {
                if(r.length > 0){
                    result[idx] = bfs(r);
                }
            });
        }
        if(check()){
            let max = 0;
            for(let i=0; i < N; i++){
                for(let j = 0; j< M; j++){
                    if(tomatos[i][j].distance > max){max = tomatos[i][j].distance;}
                }
            }
            console.log(max);
        }else{
            console.log(-1);
        }
    }

30 19
0 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1
-1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

맞은 출력 : 13

오답 : 22

가 뜨네요.

지금 보이는 로직상 단계별로 딱 1개씩만 pop을 해서 하는 방식이라 생기는 문제 같네요

(0, 18)/(0, 19)/(0,21)/(0,22)의 위치에서 잘못된 거리가 저장이 되고 있습니다.

(0,4)에 위치한 토마토와 (5,26)에 위치한 토마토가 있는데,

거리상으로는 (5,26)의 토마토가 위의 (0,22),(0,21)의 토마토의 거리가 가까우므로 이 위치에서 출발한 것들이 저장되어야하는데

지금 하신 방법으로는 (0,4)에 위치한 토마토가 움직였을때로 저장이 되더군요.

그래서 위의 bfs로직을 좀 바꾸시면 될것 같아요.

제가 자바스크립트를 잘 알지못해서 제대로 파악은 못했지만,

최초의 토마토로 한번 움직인 결과를 각각의 result의 idx에 저장시켜놓은다음에 그 결과물을 bfs함수를 한번씩 실행시키고 그 다음 반복문으로 넘어가는것 같았습니다.

이럴 경우, result 각 인덱스에 저장된 Array들의 거리가 천차만별이 되어서 제대로된 BFS를 하지못해서 서로의 경계점에서 잘못된 결과가 저장되는 것 같습니다.

else if문을 통해 갱신이 되지만, 그 갱신이 된 새로운 위치가 queue에 들어가지 않기 때문에, 짧은거리로 다시 탐색을 하지 못하게 되어서 원하시던 결과가 나오지 않는것 같습니다.

queue = [[row+dx[i],col+dy[i]],...queue]를 else if문에 넣는 방도도 있지만, 이렇게 할 시 시간초과가 뜹니다.

그래서 코드의 bfs를 한번만 pop 하던거에서 한번 bfs에 들어오면 그 queue에 있는 것을 전부 pop하여 새로운 것들만 temp라는 Array에 넣어주고 반환해주는 방식으로 했습니다.

이렇게 할경우 bfs에 있었던 else if를 생략이 가능해집니다.

왜냐하면 방문한 것들은 제일 짧은 위치에서 방문을 한것이기 때문에, 불필요한 로직이 줄어들게 됩니다.

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let N = +input[0].split(' ')[1];
let M = +input[0].split(' ')[0];

class Tomato{
    constructor(data){
        this.data = data;
        this.parent = null;
        this.isInQueue = false;
        this.distance = 0;
    }
    setParent(i,j){
        this.parent = [i,j];
    }

    setDistance(nodes){
        this.distance = nodes[this.parent[0]][this.parent[1]].distance + 1;
    }

    getParentDis(nodes){
        return nodes[this.parent[0]][this.parent[1]].distance;
    }

}
//일단 시작부터 다 익은 토마토의 위치를 파악한다.
let box = new Array(N);
let points = [];
let tomatos = Array.from(Array(N), () => new Array(M));
for(let i = 0; i < N; i++){
    box[i] = input[i+1].split(' ').map(x => +x);
    for(let j = 0; j < M; j++){
        if(box[i][j] === 1){
            points.push([i,j]);
            tomatos[i][j] = new Tomato(1);
        }else if(box[i][j] === 0){
            tomatos[i][j] = new Tomato(0);
        }else{
            tomatos[i][j] = new Tomato(-1);
        }
    }
}

let check = () => {
    for(let i = 0; i < N; i++){
        for(let j = 0; j < M; j++){
            if(tomatos[i][j].data === 0){return false;}
        }
    }
    return true;
}

let empty = () => {
    let count = 0; 
    for(let i = 0; i < N; i++){
        for(let j = 0; j < M; j++){
            if(tomatos[i][j].data === -1){count++;}
        }
    }
    return count;
}


let dx = [0,0,-1,1];
let dy = [-1,1,0,0];

if(points.length === N * M || empty() === N * M){console.log(0);}
else{
    //모든 토마토가 익기 위한 일수를 센다.
    let visited = Array.from(Array(N), () => new Array(M).fill(false));
    let bfs = (queue) => {
      let temp = []
      while(queue.length>0){
        let start = queue.pop();
        let row = start[0], col = start[1];
        visited[row][col] = true;
        tomatos[row][col].data = 1;
        tomatos[row][col].setParent(row,col);
        //child 찾기
        for(let i = 0; i < 4; i++){
            if(row+dx[i] >= 0 && row+dx[i] <= N-1 && col+dy[i] >= 0 && col+dy[i] <= M-1 ){
                if(box[row+dx[i]][col+dy[i]] === 0 && !tomatos[row+dx[i]][col+dy[i]].isInQueue && !visited[row+dx[i]][col+dy[i]]){
                   temp = [[row+dx[i],col+dy[i]],...temp];
                   tomatos[row+dx[i]][col+dy[i]].isInQueue = true;
                   tomatos[row+dx[i]][col+dy[i]].setParent(row,col);
                   tomatos[row+dx[i]][col+dy[i]].setDistance(tomatos);
                }
            }
            }

      }
            return temp;
        }
        let result = [];
        for(let i=0; i<points.length; i++){
            result.push(bfs([points[i]]));
        }
        while(result.filter(r => r.length > 0).length > 0){
            result.forEach((r,idx) => {
                if(r.length > 0){
                    result[idx] = bfs(r);
                }
            });
        }
        if(check()){
            let max = 0;
            for(let i=0; i < N; i++){
                for(let j = 0; j< M; j++){
                    if(tomatos[i][j].distance > max){max = tomatos[i][j].distance;}
                }
            }
            console.log(max);
        }else{
            console.log(-1);
        }
    }

qorgkr26 3년 전 0

아 진짜 너무 감사합니다 ㅠㅠ 토마토의 지옥에서 곧 나올 수 있겠군요.

설명 주신 거 찬찬히 읽어봤는데 결국 한 번의 bfs 호출 시, 한 번만 탐색을 한 게 실패 요인이었군요.

정말 너무 감사합니다.

적게 일하고 많이 버세요.. ㅎㅎ

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

문제

문제

출처

ICPC

[node.js] 자바스크립트 고수들 이거 좀 봐주세요

qorgkr26 3년 전 0

gkgg123 3년 전 1

qorgkr26 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말