[JS][백준]14699_관악산 등산

문제 번호

14699번: 관악산 등산

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론

 

문제 풀이

 모든 정점마다 BFS를 시도했을 때는 메모리 초과에 걸렸고, DFS를 시도했을 때는 시간 초과에 걸렸다. 그래서 위상 정렬을 생각해 봤는데 이 문제에 어떻게 활용해야 할지 모르겠어서 다른 방법을 생각해봤다.

 각 노드 까지의 거리가 아니라 각 노드부터 위로 올라가는 형식이기 때문에 위에서부터 거꾸로 내려오면서 쉼터의 개수를 세어보기로 했다.

 

 생각해보니 탐색의 시작을 위에서 부터 할 필요는 없었다. 어차피 모든 노드를 검사할 것이기 때문이었다. 대신에 각각의 노드에서 위로 올라가면서 거치는 쉼터의 수를 갱신할 때 '이전' 쉼터의 정보가 필요한데 이때의 '이전'은 아래 있는 쉼터가 아니라 위에 있는 쉼터이다. 위에서부터 내려오면서 쉼터의 개수를 세어보기로 했기 때문이다.

 그래서 map 이라는 배열을 만들어서 내려가는 방향의 정보를 넣어주기로 했다.

  for (let i = 2; i < 2 + M; i++) {
    let [a, b] = input[i].split(' ').map(Number);

    // 내려가는 방향.
    if (h[a - 1] < h[b - 1]) {
      map[a].push(b); // a에서 b로 간다.     
    }
    if (h[b - 1] < h[a - 1]) {
      map[b].push(a);  // b에서 a로 간다.     
    }
  }

 

 

이제 모든 노드에 대해서 탐색을 진행한다.

  for (let i = 1; i <= N; i++) {
    answer += sol(i) + '\n';
  }

 

 각 노드에 대해서 이미 들린 적이 있는 노드면 해당 값을 반환한다

  if (dp[cur] !== 1)
    return dp[cur];

 

그렇지 않으면 해당 노드 '이전'노드들의 값들 중 가장 큰 값을 찾아봐야 한다. 현재 노드(cur)보다 위에 있는 노드들 중에서 현재 노드와 연결되어있는 노드들을 모두 찾아본다. 그러면서 '현재 DP[cur]의 값'과 '이전노드 + 1' 의 값 중 어느 것이 더 큰지 비교하면서 DP를 갱신해주는 것이다. 여러 개의 상위 노드에서 도착할 수 있는 노드라 하더라도 결국은 상위 노드로, 방문한 노드가 나오거나 끝에 있는 노드가 나올때 까지 거슬러 올라가기 때문에 이상 없이 해당 값들을 경신할 수 있다.

  else {
    for (let next = 0; next < map[cur].length; next++) {  // 이전 노드들을 검색한다.
      dp[cur] = Math.max(dp[cur], sol(map[cur][next])+1)
    }
  }

 

전체코드

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);  // 정점, 간선.
let h = input.slice(1, 2)[0].trim().split(' ').map(Number);
let map = new Array(N + 1).fill(null).map(_ => []);
let dp = new Array(N + 1).fill(1);

function main() {
  let answer = '';

  for (let i = 2; i < 2 + M; i++) {
    let [a, b] = input[i].split(' ').map(Number);

    // 내려가는 방향.
    if (h[a - 1] < h[b - 1]) {
      map[a].push(b); // a에서 b로 간다.
    }
    if (h[b - 1] < h[a - 1]) {
      map[b].push(a);  // b에서 a로 간다.    
    }
  }
  for (let i = 1; i <= N; i++) {
    answer += sol(i) + '\n';
  }

  return console.log(answer.trim());
}
function sol(cur) {
  if (dp[cur] !== 1)
    return dp[cur];
  else {
    for (let next = 0; next < map[cur].length; next++) {  // 이전 노드들을 검색한다.
      dp[cur] = Math.max(dp[cur], sol(map[cur][next])+1)
    }
  }  
  return dp[cur];
}
main();

특이사항

 혼자서 해결하기가 어려워서 다른 분들의 팁을 참고하여 풀었다.