백준 1516 : 게임 개발 - javascript(dp , 위상정렬)

문제 출처 

https://www.acmicpc.net/problem/1516

 

정답 풀이 

위상 정렬 (Topological Sort)을 사용하여 해결할 수 있다. 

문제에서 각 건물을 짓기 위해 필요한 시간과 그 건물의 선행 조건을 만족해야 하는 다른 건물들이 제시된다. 

 

- 위상 정렬을 통해 건설 순서를 찾고, 

- 각 건물이 건설되기까지 걸리는 시간을 계산한다. 

 

기본 과정 

1. 각 건물마다 걸리는 건설 시간 저장 

2. 각 건물에 대해 먼저 지어야 하는 건물의 관계를 그래프로 저장 

3. 위상 정렬을 수행하면서, 각 건물의 최대 건설 시간을 계산

 

### 위상 정렬이란? 

위상 정렬은 방향성이 있는 비순환 그래프 에서 각 노드를 순서대로 나열하는 방법이다. 즉, 선행 조건을 가지는 작업들을 그 조건에 맞게 처리하는 순서를 결정할 때 사용하는 알고리즘이다. 그래프의 각 간선은 방향성을 가지며, 어떤 정점 u에서 v로의 간선이 있을 때 u가 먼저 나와야 하고, v는 그 뒤에 나온다. 

 

위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다. 이는 특정 작업이 먼저 끝나야 그 다음 작업을 진행할 수 있는 문제, 또는 컴파일러가 코드를 컴파일할 때 함수의 호출 순서를 결정하는 문제에서 활용된다.

 

위상 정렬의 핵심 개념 

1. 진입차수 : 특정 노드로 들어오는 간선의 개수를 의미한다. 진입 차수가 0인 노드는 다른 노드에 의해 선행되지 않으므로 바로 처리할 수 있는 노드다. 

2. 큐를 사용한 처리 : 진입 차수가 0인 노드를 큐에 넣고, 그 노드를 처리하면서 후속 노드의 진입 차수를 하나씩 감소시킨다. 후속 노드의 진입 차수가 0이 되면 그 노드도 큐에 넣는다. 이를 반복해서 전체 노드를 처리한다. 

 

위상 정렬의 과정 

1. 진입 차수가 0인 노드를 큐에 넣는다. 

2. 큐에서 노드를 꺼내어 그 노드와 연결된 간선들을 제거한다. 

3. 후속 노드들의 진입 차수를 하나씩 감소시킨다. 

4. 진입 차수가 0이 된 노드를 큐에 넣는다. 

5. 큐가 빌 때까지 이 과정을 반복한다. 

정답 코드 

const readline = require('readline'); 
const rl = readline.createInterface({
    input: process.stdin, 
    output: process.stdout
})
let input =[]; 
rl.on('line', function(line){
    input.push(line)
}).on('close', function(){
    const N = parseInt(input[0])
    const time = new Array(N+1).fill(0)
    const graph = Array.from({length: N+1}, () => [])
    const indegree = new Array(N+1).fill(0)
    const answer = new Array(N+1).fill(0)
    
    for(let i=1; i<N+1; i++){
        const info = input[i].split(' ').map(v => +v)
        time[i] += info[0]
        for(let j=1; j<info.length-1; j++){
          const pre = info[j]
          graph[pre].push(i) 
          indegree[i]++; 
        }
    }
    
    const queue = []; 
    for(let i=1; i<N+1; i++){
        if(indegree[i] === 0){
            queue.push(i)
            answer[i] = time[i]
        }
    }
    
    while(queue.length){
       const now = queue.shift()
       for(let next of graph[now]){
           answer[next] = Math.max(answer[next], answer[now] + time[next]); 
           indegree[next]--; 
           if(indegree[next] === 0)queue.push(next)
       }
    }
    
    for(let i=1; i<N+1; i++){
        console.log(answer[i])
    }
})


//time 시간 저장하기 
//관계 그래프 그리기 
//queue에 맞춰서 시간 update 
//-해당 큐의 그래프 뒤에 건물들 시간 update하고, indegree-- 해준다. 
//-먄약 indegree가 0이면 queue에 넣는다 
//마지막 출력

의사코드 추가 

let readline = require('readline');

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

let input = [];
rl.on('line', function(line) {
    input.push(line);
}).on('close', function() {
    const N = parseInt(input[0]); // 건물의 수
    const time = new Array(N + 1).fill(0); // 각 건물의 건설 시간
    const indegree = new Array(N + 1).fill(0); // 각 건물의 진입 차수
    const graph = Array.from({ length: N + 1 }, () => []); // 건물의 선행 건물을 저장할 그래프
    const result = new Array(N + 1).fill(0); // 각 건물이 건설되기까지의 최종 시간

    // 입력을 처리하여 건물 관계 및 시간을 초기화
    for (let i = 1; i <= N; i++) {
        const data = input[i].split(' ').map(Number);
        time[i] = data[0]; // 건물 i의 건설 시간
        for (let j = 1; j < data.length - 1; j++) { // -1을 제외하고, 선행 건물들을 처리
            const preBuilding = data[j];
            graph[preBuilding].push(i); // preBuilding을 먼저 지어야 i를 지을 수 있음
            indegree[i]++; // i 건물로 들어오는 간선 수 증가
        }
    }

    // 위상 정렬을 위한 큐
    const queue = [];
    for (let i = 1; i <= N; i++) {
        if (indegree[i] === 0) {
            queue.push(i); // 진입 차수가 0인 건물은 바로 건설 가능
            result[i] = time[i]; // 초기 건설 시간 설정
        }
    }

    // 위상 정렬
    while (queue.length) {
        const current = queue.shift(); // 큐에서 하나씩 꺼냄

        // 현재 건물을 짓고 나서 지을 수 있는 다른 건물들 확인
        for (let next of graph[current]) {
            indegree[next]--; // 해당 건물의 진입 차수 감소
            result[next] = Math.max(result[next], result[current] + time[next]); // 최대 건설 시간 갱신
            if (indegree[next] === 0) {
                queue.push(next); // 진입 차수가 0이 되면 큐에 추가
            }
        }
    }

    // 결과 출력
    for (let i = 1; i <= N; i++) {
        console.log(result[i]);
    }
});