[Algorithm] 등산코스 정하기

📋 문제

XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.

등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.
예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.

당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.

다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.

• 위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다. 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다. 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.

위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다. 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.

등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다. 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.

XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.

제한사항

• 2 ≤ n ≤ 50,000
• n - 1 ≤ paths의 길이 ≤ 200,000
• paths의 원소는 [i, j, w] 형태입니다.
  
  • i번 지점과 j번 지점을 연결하는 등산로가 있다는 뜻입니다.
  • w는 두 지점 사이를 이동하는 데 걸리는 시간입니다.
  • 1 ≤ i < j ≤ n
  • 1 ≤ w ≤ 10,000,000
  • 서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개입니다.
• 1 ≤ gates의 길이 ≤ n
  
  • 1 ≤ gates의 원소 ≤ n
  • gates의 원소는 해당 지점이 출입구임을 나타냅니다.
• 1 ≤ summits의 길이 ≤ n
  
  • 1 ≤ summits의 원소 ≤ n
  • summits의 원소는 해당 지점이 산봉우리임을 나타냅니다.
• 출입구이면서 동시에 산봉우리인 지점은 없습니다.
• gates와 summits에 등장하지 않은 지점은 모두 쉼터입니다.
• 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
• return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.

입출력 예

6	[[1, 2, 3], [2, 3, 5], [2, 4, 2], [2, 5, 4], [3, 4, 4], [4, 5, 3], [4, 6, 1], [5, 6, 1]]	[1, 3]	[5]	[5, 3]
7	[[1, 4, 4], [1, 6, 1], [1, 7, 3], [2, 5, 2], [3, 7, 4], [5, 6, 6]]	[1]	[2, 3, 4]	[3, 4]
7	[[1, 2, 5], [1, 4, 1], [2, 3, 1], [2, 6, 7], [4, 5, 1], [5, 6, 1], [6, 7, 1]]	[3, 7]	[1, 5]	[5, 1]
5	[[1, 3, 10], [1, 4, 20], [2, 3, 4], [2, 4, 6], [3, 5, 20], [4, 5, 6]]	[1, 2]	[5]	[5, 6]

 

✏️ 풀이

1. 틀린 풀이(플로이드와샬 - 시간초과)

처음에 문제를 보고 어떻게 풀지 잘 모르겠어서 플로이드와샬을 돌리기로 했다.

 

우선 최대 가중치(소요시간)를 의미하는 weight라는 이차원배열을 선언했다. 이때 최소값을 구하지만 가는 길목의 최대 소요시간을 구하기 때문에 각 요소는 0으로 초기화했다.

 

삼중for문을 이용해서 플로이드와샬을 돌렸는데 만약 기준이 되는 지점이 산봉오리라면 계산하지 않아야 하기 때문에 (산봉오리를 거쳐 다른 산봉오리로 이동하는 경로 발생) summitsCheck라는 산봉오리를 담고 있는 Set 변수를 만들어줬다.

 

i에서 j로 이동할 때의 소요 시간과 i에서 k, k에서 j로 이동할 때(k를 거쳐갈 때) 걸리는 최대 소요시간을 비교하고 이전에 만들어둔 weight 배열에 갱신해준다.

 

출입구와 산봉오리를 반복문으로 돌면서 갈 수 없을 때(weight[출입구][산봉오리]가 0일 때)를 제외하고 갈 수 있을 때 answer를 최신화해줬다.

 

이렇게 문제를 풀어보니 시간초과가 발생했고 해결할 수 없었다. 따라서 다른 풀이 방법을 고민했다.

 

1. 정답 풀이(BFS)

출입구를 기준으로 DFS 또는 BFS를 돌리는 건 어떨까라는 생각을 하게 되었고 먼저 DFS를 돌렸다.

 

이때 check라는 n+1 길이의 배열을 만들어줬는데 이는 각각의 출입구에서 출발해서 해당 지점까지 갈 때의 엣지 중 최대 소요시간을 의미하고 최소값을 저장해야 하기 때문에 Infinity로 초기화시켰다.

 

먼저 그래프화 시켜주고 DFS를 돌면서 산봉오리를 만나면 더 이상 진행하지 않아야 하기 때문에 위 풀이와 동일하게 summitsCheck라는 산봉오리를 가진 Set을 만들어줬다.

 

현재 지점에서 갈 수 있는 지점을 반복문으로 도는데 이때 해당 지점까지 갈 때의 최대 시간이 check에 저장된(이전에 방문해서 갱신한 시간)보다 큰 경우에는 더이상 진행하지 않도록 했다. 또한 어떤 지점에서 다음 지점으로 갈 때 소요시간보다 check에 저장된 시간이 적다면 마찬가지로 더 이상 진행하지 않는다. 이 두 상황에 해당하지 않는다면 check를 더 작은 값으로 갱신할 수 있는 상황이므로 check를 갱신한다. 갱신 이후에 해당 지점이 만약 산봉오리라면 더 이상 진행하지 않는다.

 

DFS를 돌렸을 때는 두 개의 테스트케이스에서 시간초과가 발생했다. graph를 객체가 아닌 Map자료구조로 선언해보았지만 마찬가지였고 고민에 빠졌다. 배열을 이용한 DFS, BFS에서 DFS는 pop()을 사용하고 BFS는 shift()를 사용하기 때문에 DFS를 돌렸던 것인데 출입구부터 시작해서 산봉오리로 다가갈 때 DFS를 돌 때 계속 갱신할 수 있는 상황이 발생할 수 있다고 생각했다. 

 

DFS의 경우 출입구1부터 시작했을 때 모든 지점을 돌면서 최대 소요시간을 2로 갱신한다. 하지만 다음 출입구2를 돌면 모두 1로 초기화해야한다. 하지만 BFS를 돌렸을 때 제일 처음 출입구들과 연결된 지점에서만 중복이 발생하고 다머지는 한번만 수행될 것이다. 따라서 BFS로 변경했고 결과적으로 문제를 해결할 수 있었다.

⌨️  시간초과 코드

function solution(n, paths, gates, summits) {
  var answer = [0, Infinity];

  const weight = [...Array(n + 1)].map(_ => new Array(n + 1).fill(0));
  for (const path of paths) {
    const [n1, n2, w] = path;
    weight[n1][n2] = w;
    weight[n2][n1] = w;
  }

  const summitsCheck = new Set();
  for (const summit of summits) summitsCheck.add(summit);

  for (let k = 1; k < n + 1; k++) {
    if (summitsCheck.has(k)) continue;

    for (let i = 1; i < n + 1; i++) {
      for (let j = 1; j < n + 1; j++) {
        if (!weight[i][k] || !weight[k][j]) continue;

        const min = Math.max(weight[i][k], weight[k][j]);
        if (weight[i][j]) {
          if (weight[i][j] > min) weight[i][j] = min;
        } else weight[i][j] = min;
      }
    }
  }

  summits.sort((a, b) => a - b);
  for (const gate of gates) {
    for (const summit of summits) {
      if (!weight[gate][summit]) continue;

      if (weight[gate][summit] < answer[1]) {
        answer[0] = summit;
        answer[1] = weight[gate][summit];
      }
    }
  }

  return answer;
}

 

⌨️  정답 코드

function solution(n, paths, gates, summits) {
  var answer = [0, Infinity];

  const graph = {};
  for (const path of paths) {
    const [n1, n2, w] = path;
    if (graph[n1]) graph[n1].push([n2, w]);
    else graph[n1] = [[n2, w]];
    if (graph[n2]) graph[n2].push([n1, w]);
    else graph[n2] = [[n1, w]];
  }

  const summitsCheck = new Set();
  for (const summit of summits) summitsCheck.add(summit);

  const queue = gates.map(gate => [gate, 0]);

  const check = new Array(n + 1).fill(Infinity);
  while (queue.length) {
    const [node, min] = queue.shift();
    for (const [next, w] of graph[node]) {
      if (check[next] <= w) continue;
      if (check[next] <= min) continue;
      check[next] = Math.max(w, min);

      if (summitsCheck.has(next)) continue;
      queue.push([next, check[next]]);
    }
  }

  summits.sort((a, b) => a - b);
  for (const summit of summits) {
    if (answer[1] > check[summit]) {
      answer = [summit, check[summit]];
    }
  }

  return answer;
}