[백준 1948] 임계경로

 

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

1948번: 임계경로

 

위상정렬 + 역추적 문제이다.

 

문제이해가 어려웠으나 요약하면

1. 시작점->목적지까지 도달하는데 가장 오래 걸리는 시간 구하기

2. 1만큼의 시간이 소요되는 경로에 속한 도로들의 수 구하기 이다. 

1분도 쉬지 않는다는 의미가 2라는 걸 이해하지 못했다...

 

1을 푸는 것은 위상정렬 + dp를 결합하면 어렵지 않게 해결할 수 있으나 문제는 2였다.

2에 대해 set으로 풀었으나 메모리 제한이 걸렸고 역추적이 필요함을 알게 되었다.

 

역추적을 어떻게 해야 하나 고민했는데 다른 사람들의 풀이를 참고한 결과 의외로 간단했다.

1에서 사용한 dp를 이용하여 진행한다.

이 때 주의할 점은 이미 방문한 노드에 대해서는 재확인하지 않는 다는 점이다.

visited를 체크하지 않았을 때 반례

in:

5

7

1 2 1

1 3 3

2 3 2

2 4 1

2 5 3

3 5 1

4 5 1

1 5

out:

4

5

while (!q.empty())
  {
    int top = q.front();
    q.pop();

    if (visited[top])
      continue;

    visited[top] = true;

    for (auto a : back[top])
    {
      if (dp[top] - dp[a.next] == a.cost)
      {
        q.push(a.next);
        roads++;
      }
    }
  }

 

정답코드는 다음과 같다.

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;
const int MAX = 10000 + 1;

int first, goal;
struct s
{
  int next, cost;
};

int indegree[MAX];
int dp[MAX]; //max cost 누적
bool visited[MAX];
vector<s> adj[MAX];
vector<s> back[MAX];
queue<int> q;

int main(void)
{
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++)
  {
    int from, to, cost;
    scanf("%d%d%d", &from, &to, &cost);
    adj[from].push_back({to, cost});
    back[to].push_back({from, cost}); //역추적을 위해 필요
    indegree[to]++;
  }

  scanf("%d%d", &first, &goal);
  q.push(first);

  while (!q.empty())
  {
    int top = q.front();
    q.pop();

    for (auto a : adj[top])
    {
      int next = a.next, cost = a.cost;
      indegree[next]--;

      if (dp[top] + cost > dp[next])
      {
        dp[next] = dp[top] + cost; //dp[i]는 ith 노드까지 max cost
      }

      if (indegree[next] == 0)
      {
        q.push(next);
      }
    }
  }

  int roads = 0;
  q.push(goal);

  while (!q.empty())
  {
    int top = q.front();
    q.pop();

    if (visited[top])
      continue;

    visited[top] = true;

    for (auto a : back[top])
    {
      if (dp[top] - dp[a.next] == a.cost)
      {
        q.push(a.next);
        roads++;
      }
    }
  }

  printf("%d\n%d\n", dp[goal], roads);
  return 0;
}