[백준][C++]1948번 임계경로

문제

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

1948번: 임계경로

 

 

풀이

1. 정방향 위상 정렬 수행

• 시작점 : 출발 도시
• 각 도시와 관련된 임계 경로 저장

 

2. 역방향 위상 정렬 수행

• 시작점 : 도착 도시
• 현재 임계 경로값 + 해당 도로값 == 이전 도시의 임계 경로값 ⇒ 1분도 쉬지 않고 달려야 하는 도로로 저장

 

위상 정렬(Topology Sort) 알고리즘

위상 정렬(Topology Sort) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m;	// 도시 수, 도로 수
  cin >> n >> m;

  vector<vector<pair<int, int>>> outcity(n + 1);	// 도시 인접 리스트
  vector<vector<pair<int, int>>> incity(n + 1);	// 역방향 도시 인접 리스트
  vector<int> indegree(n + 1, 0);	// 진입 차수 배열
  vector<int> time(n + 1, 0);
  for(int i = 0; i < m; i++)
  {
    int s, e, c;
    cin >> s >> e >> c;

    outcity[s].push_back(make_pair(e, c));
    incity[e].push_back(make_pair(s, c));	// 역방향 에지 정보 저장
    indegree[e]++;	// 진입 차수 배열 초기화
  }

  int start, end;
  cin >> start >> end;
  
  queue<int> myqueue;	// 큐 생성하기
  // 위상 정렬 수행
  myqueue.push(start);	// 출발 도시를 큐에 삽입
  while(!myqueue.empty())
  {
    int now_city = myqueue.front();
    myqueue.pop();

    for(pair<int, int> next : outcity[now_city])
    {
      int next_city = next.first;
      int cost = next.second;

      time[next_city] = max(time[next_city], time[now_city] + cost);
      if(--indegree[next_city] == 0)
      {
        myqueue.push(next_city);	// 큐에 타깃 노드 추가
      }
    }
  }

  cout << time[end] << "\n";	// 만나는 시간 출력
  
  // 위상 정렬 reverse
  vector<bool> visited(n + 1, false);	// 각 도시의 방문 여부 저장
  visited[end] = true;
  int count = 0;	// 1분도 쉬지 않고 달려야 하는 도로의 수
  myqueue.push(end);	// 도착 도시를 큐에 삽입
  while(!myqueue.empty())
  {
    int now_city = myqueue.front();
    myqueue.pop();
    
    for(pair<int, int> before : incity[now_city])
    {
      int before_city = before.first;
      int cost = before.second;
      // 1분도 쉬지 않는 도로 체크
      if(time[now_city] == time[before_city] + cost)
      {
        count++;	// 1분도 쉬지 않고 달려야 하는 도로값 1 증가
        // 중복 카운트 방지를 위해 이미 방문한 노드 제외
        if(visited[before_city] == false)
        {
          visited[before_city] = true;	// visited 배열에 방문 도시 표시
          myqueue.push(before_city);	// 큐에 타깃 노드 추가
        }
      }
    }
  }

  cout << count;	// 1분도 쉬지 않고 달려야 하는 도로의 수 출력

  return 0;
}

 

 

오답

• 정방향 위상 정렬 수행 시, 타깃 노드의 진입 차수가 0일 경우 큐에 타깃 노드 추가
• 역방향 위상 정렬 수행 시, 아직 방문하지 않은 도시이면 큐에 타깃 노드 추가

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, M;
  cin >> N >> M;

  vector<vector<pair<int, int>>> A;
  vector<vector<pair<int, int>>> reverseA;
  vector<int> indegree;  // 진입 차수 배열
  A.resize(N + 1);
  reverseA.resize(N + 1);
  indegree.resize(N + 1);
  
  for(int i = 0; i < M; i++)
  {
    int S, E, V;
    cin >> S >> E >> V;
    A[S].push_back(make_pair(E, V));
    reverseA[E].push_back(make_pair(S, V));  // 역방향 에지 정보 저장
    indegree[E]++;  // 진입 차수 배열 초기화
  }

  int startDosi, endDosi;
  cin >> startDosi >> endDosi;
  queue<int> mqueue;
  // 위상 정렬 수행
  mqueue.push(startDosi);
  vector<int> result;
  result.resize(N + 1);

  while(!mqueue.empty())
  {
    int now = mqueue.front();
    mqueue.pop();

    for(pair<int, int> next : A[now])
    {
      indegree[next.first]--;
      result[next.first] = max(result[next.first], result[now] + next.second);
      if(indegree[next.first] == 0)
      {
        mqueue.push(next.first);
      }
    }
  }
  // 위상 정렬 reverse
  int resultCount = 0;
  vector<int> visited;
  visited.resize(N + 1);
  queue<int> rqueue;
  rqueue.push(endDosi);
  visited[endDosi] = true;

  while(!rqueue.empty())
  {
    int now = rqueue.front();
    rqueue.pop();

    for(pair<int, int> next : reverseA[now])
    {
      // 1분도 쉬지 않는 도로 체크
      if(result[next.first] + next.second == result[now])
      {
        resultCount++;
        // 중복 카운트 방지를 위해 이미 방문한 노드 제외
        if(visited[next.first] == false)
        {
          visited[next.first] = true;
          rqueue.push(next.first);
        }
      }
    }
  }
  cout << result[endDosi] << "\n";
  cout << resultCount << "\n";
}