백준 1005 : ACM Craft

풀이1 : 시간 초과

• 제약 없이 지을 수 있는 건물들을 시작점으로 설정, 다음 노드로 이동할 경우 visited배열에 입력된 값 보다 큰 값일 경우에만 이동했다.
• 예제 케이스는 통과. 로직 문제인줄 알았는데 입력을 받는 부분에서부터 시간 초과가 발생한다.

var fs = require("fs")

// 줄바꿈으로 구분
const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');


let caseNum = stdin.shift();
let caseAry = [];

while(caseNum > 0){
    let temp = {};
    temp.infoAry = stdin.shift().split(" ").map(Number);
    temp.buildTimes = stdin.shift().split(" ").map(Number);
    temp.buildTimes.unshift(0);
    let edges = []
    for(let i = 0; i < temp.infoAry[1]; i++){
        edges[i] = stdin.shift().split(" ").map(Number);
    }
    temp.edges = edges;
    temp.target = Number(stdin.shift());

    caseAry.push(temp);
    caseNum--;
}


function compTime(caseObj){
    
    let resultTime = 0;
    //간선들을 나타낼 배열
    let map = [];
    for(let i = 0; i < caseObj.infoAry[0]+1; i++){
        map.push(new Array(caseObj.infoAry[0]+1).fill(0));
    }

    
    for(let i = 0; i < caseObj.edges.length; i++){
        map[caseObj.edges[i][0]][caseObj.edges[i][1]] = 1;
    }
    

    //시작점이 될 수 있는 건물들(건설의 요구조건이 없는 건물들)
    let startbuilds = [];
    for(let col = 1; col < map.length; col++){
        let flag = true
        for(let row = 1; row < map.length; row++){
            if(map[row][col] === 1) {
                flag = false;
                break;
            }
        }
        if(flag) startbuilds.push(col);
    
    }
 

    startbuilds.forEach(e => {
        resultTime = Math.max(resultTime, bfs(caseObj, e, map));
    })


    return resultTime;

}

function bfs(caseObj, start, map){
    //시작점에서 현재 점까지 걸리는 시간을 담을 배열
    let visited = new Array(caseObj.infoAry[0]+1).fill(0);
    let queue = [start];
    visited[start] = caseObj.buildTimes[start];
    let result = 0;

    while(queue.length > 0){
        let curbuilding = queue.shift();
        //목표 건물 건설
        if(curbuilding === caseObj.target){
            result = Math.max(visited[curbuilding], result);
        }

        for(let i = 1; i < map.length; i++){
            //다음 노드로 이동, 다음 노드로 이동할때 까지 걸리는 최대 시간을 visited배열에 넣는다.
            if(map[curbuilding][i] === 1){
                //만약 최대 비용이 되지 않으면 큐에 넣지 않는다
                if(visited[i] > visited[curbuilding] + caseObj.buildTimes[i]) continue;
                queue.push(i);
                visited[i] = Math.max(visited[i], visited[curbuilding] + caseObj.buildTimes[i]);
            }
        }
    }

    return result;
}

caseAry.forEach(obj => {
    console.log(compTime(obj));
})

풀이2 : 시간 초과

• shift()함수가 O(n)의 시간복잡도를 가진다고 한다. 입력받는 부분을 수정해 보았다.
• 그 외에도 배열의 선언, 반복문 호출을 최소화 했으나 시간 초과가 발생했다.
• map 배열 대신 간선들을 그대로 이용해 보기

let caseNum = stdin[0];
let caseAry = [];
let curIdx = 1;

while(caseNum > 0){
    let temp = {};
    temp.infoAry = stdin[curIdx].split(" ").map(Number);
    temp.buildTimes = stdin[curIdx+1].split(" ").map(Number);
    temp.buildTimes.unshift(0);
    let edges = []
    for(let j = 0; j < temp.infoAry[1]; j++){
        edges[j] = stdin[curIdx+2+j].split(" ").map(Number);
    }
    temp.edges = edges;
    temp.target = Number(stdin[curIdx+3+temp.infoAry[1]-1]);

    caseAry.push(temp);
    curIdx = curIdx+3+temp.infoAry[1];
    caseNum--;
}

function compTime(caseObj){
    //간선들을 나타낼 배열
    let map = [];
    for(let i = 0; i < caseObj.infoAry[0]+1; i++){
        map.push(new Array(caseObj.infoAry[0]+1).fill(0));
    }

    
    for(let i = 0; i < caseObj.edges.length; i++){
        map[caseObj.edges[i][0]][caseObj.edges[i][1]] = 1;
    }
    
    let queue = [];
    let visited = [...caseObj.buildTimes];
    //시작점이 될 수 있는 건물들(건설의 요구조건이 없는 건물들)
    for(let col = 1; col < map.length; col++){
        let flag = true
        for(let row = 1; row < map.length; row++){
            if(map[row][col] === 1) {
                flag = false;
                break;
            }
        }
        if(flag) {
            queue.push(col);
        }
    
    }

    //BFS
    while(queue.length > 0){
        let curbuilding = queue.shift();
        if(curbuilding === caseObj.target) continue;

        for(let i = 1; i < map.length; i++){
            //다음 노드로 이동, 다음 노드로 이동할때 까지 걸리는 최대 시간을 visited배열에 넣는다.
            if(map[curbuilding][i] === 1){
                //만약 최대 비용이 되지 않으면 큐에 넣지 않는다
                if(visited[i] > visited[curbuilding] + caseObj.buildTimes[i]) continue;
                queue.push(i);
                visited[i] = visited[curbuilding] + caseObj.buildTimes[i];
            }
        }
    }




    return visited[caseObj.target];

}


caseAry.forEach(obj => {
    console.log(compTime(obj));
})

풀이3

• 위상정렬(topological sorting. 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열)을 이용했다.
• 노드 방문에 선행 노드 방문이 필요한 경우 사용
• 위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않아야 한다. 비순환 유향 그래프(DAG. directed acyclic graph)여야 한다.
• 단방향 그래프이기 때문에 노드 간의 연결 상태를 나태낼 때 N*N의 배열을 만들지 않아도 된다.
• 노드를 큐에 넣기 전, 선수 노드의 충족을 나타내는 'endPointAry'배열을 사용했다.

var fs = require("fs")

// 줄바꿈으로 구분
const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');


let caseNum = stdin[0];
let caseAry = [];
let curIdx = 1;

while(caseNum > 0){
    let temp = {};
    temp.infoAry = stdin[curIdx].split(" ").map(Number);
    temp.buildTimes = stdin[curIdx+1].split(" ").map(Number);
    temp.buildTimes.unshift(0);
    let edges = []
    for(let j = 0; j < temp.infoAry[1]; j++){
        edges[j] = stdin[curIdx+2+j].split(" ").map(Number);
    }
    temp.edges = edges;
    temp.target = Number(stdin[curIdx+3+temp.infoAry[1]-1]);

    caseAry.push(temp);
    curIdx = curIdx+3+temp.infoAry[1];
    caseNum--;
}
    

function compTime(caseObj){
    //시작점을 찾기위해 해당 노드가 목적지가 되는 경우를 저장한다
    let endPointAry = new Array(caseObj.infoAry[0]+1).fill(0);
    // 간선들을 나타낼 배열
    let map = [];
    for(let i = 0; i < caseObj.infoAry[0]+1; i++){
        map.push([]);
    }

    for(let i = 0; i < caseObj.edges.length; i++){
        map[caseObj.edges[i][0]].push([caseObj.edges[i][1]]);
        endPointAry[caseObj.edges[i][1]]++;
    }
    
    let queue = [];
    let visited = [...caseObj.buildTimes];
    //시작점이 될 수 있는 건물들(건설의 요구조건이 없는 건물들)
    for(let i = 1; i < endPointAry.length; i++){
        if(endPointAry[i] === 0) queue.push(i);
    }

    //BFS
    while(queue.length > 0){
        let curbuilding = queue.shift();

        //현재 건물에서 다음 건물들의 배열을 전부 조회
        map[curbuilding].forEach(nextNode => {
            visited[nextNode] = Math.max(visited[nextNode], visited[curbuilding]+caseObj.buildTimes[nextNode]);
            endPointAry[nextNode]--;

            //건설 가능한 경우 큐에 넣는다
            if(endPointAry[nextNode]===0) queue.push(nextNode);
        })

    }

    return visited[caseObj.target];

}



caseAry.forEach(obj => {
    console.log(compTime(obj));
})