BOJ-백준 1948번 임계경로 C++

BOJ-백준 1948번 임계경로 C++ 문제 풀이 입니다.

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

1948번: 임계경로

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10001

using namespace std;

class Edge{
  public:
  int node;
  int time;
  Edge(int node, int time){
    this->node = node;
    this->time = time;
  }
};

int n, start, finish;
int inDegree[MAX], result[MAX], c[MAX]; 
// c : 처리가 되었는지 확인 여부 저장
vector<Edge> a[MAX]; 
vector<Edge> b[MAX];

void topology() {
  queue<int> q; 
  q.push(start);
  while(!q.empty()){
    int x= q.front();
    q.pop();
    for(int i=0; i< a[x].size(); i++){
      Edge y = Edge(a[x][i].node, a[x][i].time);
      if(result[y.node]<=y.time + result[x]){
        result[y.node] = y.time + result[x];
      }
      if(--inDegree[y.node] == 0) {
        q.push(y.node);
      }
    }
  }
  int count = 0;
  q.push(finish);
  while(!q.empty()){
    int y = q.front();
    q.pop();
    for(int i=0; i < b[y].size(); i ++) { 
      Edge x = Edge(b[y][i].node, b[y][i].time);
      if(result[y] - result[x.node] == x.time){
        count ++;
        if(c[x.node] == 0) {
          q.push(x.node);
          c[x.node] = 1 ;
        }
      }
    }
  }
  printf("%d\n%d", result[finish], count);
}

int main() {
  int m;
  scanf("%d %d", &n, &m);
  for(int i=0; i<m; i++){
    int x, node, time;
    scanf("%d %d %d", &x, &node, &time);
    a[x].push_back(Edge(node,time));
    b[node].push_back(Edge(x, time));
    inDegree[node]++;
  }
  scanf("%d %d", &start, &finish);
  topology();
}

 

📌 해설

위상 정렬을 이용해 최대 비용(시간)을 구하고, 임계경로를 구하는 문제입니다. (DFS로도 해결 가능)

1. 시작 도시에서 출발하여 도착도시로 모두가 도착하는데 걸리는 최소 시간

= 위상 정렬을 이용해 최대 비용(시간)을 구함

2. 쉬지 않고 달려야 하는 도로의 개수

= 도착지점에서 역으로 시작지점으로 탐색하여 임계경로를 구하고, 지나온 도로를 count 함

임계경로
위상 정렬을 진행하면 각 작업이 어떠한 순서로 진행되어야 하는지 알 수 있습니다.
임계경로는 finish에 도달하는데 가장 오래 걸리는 경로를 의미합니다. 
즉, 방향그래프에서 위상정렬로 순서를 표현하면, 임계경로는 그 중 가장 큰 비용이 드는 경로를 의미합니다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10001

using namespace std;

class Edge{
  public:
  int node;
  int time;
  Edge(int node, int time){
    this->node = node;
    this->time = time;
  }
};

int n, start, finish;
int inDegree[MAX], result[MAX], c[MAX]; 
// c : 처리가 되었는지 확인 여부 저장
vector<Edge> a[MAX]; 
vector<Edge> b[MAX];

 1. 필요한 변수를 모두 선언합니다. 

1-1. 도시의 수는 10,000까지 입력될 수 있으므로, MAX를 10,001로 정의합니다. 

1-2. Edge 클래스를 만듭니다. node와 time이 저장됩니다. 

1-3. 도시의 수 n, 시작 노드 start, 도착 노드 finish를 선언합니다. 

1-4. 진입 차수 inDegree, 최대 비용(시간)을 기록하는 result, 방문 여부를 확인하는 c(check)를 선언합니다. 

1-5. a는 도시 연결 정보를 저장합니다. b는 역순으로 탐색할 도시 연결 정보입니다. 

 

int main() {
  int m;
  scanf("%d %d", &n, &m);
  for(int i=0; i<m; i++){
    int x, node, time;
    scanf("%d %d %d", &x, &node, &time);
    a[x].push_back(Edge(node,time));
    b[node].push_back(Edge(x, time));
    inDegree[node]++;
  }
  scanf("%d %d", &start, &finish);
  topology();
}

2. main에서 필요한 정보를 입력받고 topology()함수를 호출합니다. 

2-1. a에는 도시의 연결 정보를 입력합니다.

예를들어 도시 1에 도시 2가 연결되어있고 걸리는 시간이 4일때, 

a[1] 에는 Edge(2, 4)가 저장 됩니다. 

b에는 역순으로 탐색할 그래프를 저장하는 것이므로 

b[2] 에 Edge(1, 4)가 저장됩니다. 

2-2. node 의 진입차수 inDegree를 증가시킵니다. 

 

void topology() {
  queue<int> q; 
  q.push(start);
  while(!q.empty()){
    int x= q.front();
    q.pop();
    for(int i=0; i< a[x].size(); i++){
      Edge y = Edge(a[x][i].node, a[x][i].time);
      if(result[y.node]<=y.time + result[x]){
        result[y.node] = y.time + result[x];
      }
      if(--inDegree[y.node] == 0) {
        q.push(y.node);
      }
    }
  }

3. topology에서 위상 정렬을 진행합니다. 

3-1. 큐를 선언하고 시작 노드를 큐에 삽입합니다. 

3-2. 큐가 빌때 까지 반복하는 while문을 선언합니다. 

3-3. 큐에서 원소를 하나 빼서 x에 저장합니다. 

3-4. x 에 연결된 도시를 탐색하는 for문을 작성합니다. 

    3-4.(1) x에 연결된 도시의 정보를 Edge y에 저장합니다. 

    3-4.(2) result[y]에는 도시 y 에 도착하는데 걸린 시간이 기록됩니다. 최대 비용을 구해야 하므로 가장 큰 비용이 기록 될 수 있도록 if문을 작성합니다. 

    3-4.(3) y의 진입차수를 1 뺀 뒤, 0인지 확인하고 0이라면, 큐에 삽입합니다. 

3-5. 위 반복문이 종료되면 result[start] 부터 result[finish]까지 최대 비용이 기록됩니다. 최대 비용은 result[finish] 와 같습니다. 

 

  int count = 0;
  q.push(finish);
  while(!q.empty()){
    int y = q.front();
    q.pop();
    for(int i=0; i < b[y].size(); i ++) { 
      Edge x = Edge(b[y][i].node, b[y][i].time);
      if(result[y] - result[x.node] == x.time){
        count ++;
        if(c[x.node] == 0) {
          q.push(x.node);
          c[x.node] = 1 ;
        }
      }
    }
  }
  printf("%d\n%d", result[finish], count);
}

4. result에 기록된 최대 비용을 이용해 역순으로 start를 찾아가며 임계경로를 구하고 count 합니다. 

4-1. count를 0 으로 선언하고 초기화 합니다. 

4-2. 큐에 finish노드를 삽입합니다. 

4-3. 큐가 빌때까지 반복하는 while문을 작성합니다. 

    4-3.(1) 큐에서 원소를 하나 빼서 y에 저장합니다. 

    4-3(2) 도시 y에 연결된 모든 도시를 탐색하는 for문을 작성합니다. 

    4-3.(3) y에 연결된 도시 정보를 Edge x라고 저장합니다. 

    4-3.(4) result의 기록과 도시 정보의 time과 일치하는 노드 x가 있다면 count 합니다.

    4-3.(5) x를 재방문 하지 않도록 c[x]를 1로 변경합니다. 

    4-3.(6) 큐에 x를 삽입합니다.  

4-4. result[finish]와 count를 출력합니다.

 

 

::

 

어려워 어려워ㄷㄷ