[백준] 2307번 도로검문 c++

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

2307번: 도로검문

문제

그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고  두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다.

그림 1

예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다.

어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하려고 한다. 따라서 용의자는 이 도로를 피해서 가장 빠르게 도시를 탈출하고자 한다. 이 경우 경찰이 검문을 위하여 선택하는 도로에 따라서 용의자의 가장 빠른 탈출시간은 검문이 없을 때에 비하여 더 늘어날 수 있다.

문제는 도로검문을 통하여 얻을 수 있는 탈출의 최대 지연시간을 계산하는 것이다. 추가설명은 다음과 같다.

1. 두 개의 지점을 직접 연결하는 도로가 있는 경우, 그 도로는 유일하다. 
2. 도시의 지점(노드)은 1에서 N번까지  N개의 연속된 정수로 표시된다.
3. 용의자가 도시에 진입하는 지점은  항상 1번이고 도시를 빠져 나가기 위하여 최종적으로 도달해야하는 지점은 항상 N번 지점이다.
4. 용의자는 검문을 피해서 가장  빨리 도시를 빠져나가고자 하고, 경찰은 적절한 도로를 선택하여 이 용이자들의 탈출시간을 최대한 지연시키고자 한다.
5. 각 도시 지점 간을 이동하는 시간은 항상 양의 정수이다.

입력 도시의 도로망에 따라서 경찰이 어떤 도로를 막으면 용의자는 도시를 탈출하지 못할 수도 있다. 이 경우 검문으로 인하여 지연시킬 수 있는 탈출시간은 무한대이다. 이 경우에는 -1을 출력해야 한다.

그림 1에서 볼 때 검문이 없을 경우 용의자가 도시를 탈출하는데 걸리는 시간은 4분이다. 만일 경찰이 도로(4,3)을 막으면 그 탈출시간을 지연시킬 수 없으므로 지연시간은 0이다. 만일 도로(2,3)을 막으면, 용의자들이 가장 빠르게 탈출할 수 있는 시간은 5분이므로 탈출지연시간은 1분이고, 도로(3,6)을 막으면 탈출지연시간은 2분이다.

여러분은 입력 데이터에 표시된 도로망을 읽고, 경찰이 한 도로를 막고 검문함으로써 지연시킬 수 있는 최대시간을 정수로 출력하여야한다. 만일 지연효과가 없으면 0을 출력해야하고, 도시를 빠져나가지 못하게 만들 수 있으면(지연시간이 무한대) -1을 출력해야 한다.

입력

첫 줄에는 지점의 수를 나타내는 정수  N(6 ≤ N ≤ 1000)과 도로의 수 M(6 ≤ M ≤ 5000)이 주어진다. 그 다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 ≤ t ≤ 10000이다.

출력

경찰이 하나의 도로를 막음으로써 지연시킬 수 있는 최대 시간을 정수로 출력한다. (단, 그 지연시간이 무한대이면 -1을 출력해야 한다.)

 

 

문제접근 및 고려사항, 풀이

- dijkstra algorithm를 응용하여 풀 수 있다.

- 도로는 유일하고 양방향이며, 가중치는 양의정수이다.

- 어떤 도로를 막아 탈출 불가능하게 만들면 -1
- 도로를 막아 탈출시간을 지연할 수 있는 최대값 구하기
- 지연효과가 없으면 0이라는 것이 무엇을 의미하는 지 생각해보니 도로검문 전 부터 아예 탈출 불가능한 경우를 의미하는 것이었다.

 

1. 1번 도시에서부터 n번 도시로의 dijkstras 진행

-> 만약 탈출불가능 한 경우 0 출력(도로검문 없이도 탈출불가능하면 도로검문으로 인한 지연효과가 없으므로)

-> 도로검문 없는 경우의 용의자의 최단경로 값을 확보한다.
2. 1을 진행하면서 opt에 다가 거치는 도로들을 담는다.
3. opt에 담긴 각 도로에 대해 해당 도로를 막는 경우에 대해 dijkstras를 진행하면서 기존 최대값보다 비교하여 최대값을 갱신한다.
-> 만약 탈출불가능 (최대값이 INF)이면 -1
-> INF 아니면 기존 최소값과 차이를 구해서 max와 비교 후 갱신
-> opt는 도로검문 없은 경우의 최단경로로 고려된 도로들의 집합이므로 3에서 구한 최대값이 1에서 구한 최단경로 이동 가중치값과 같을 수 없다.

 

#include <iostream>
#include <vector>
#include <queue>
#define VMAX 1001
#define INF 987654321

using namespace std;

vector<pair<int,int>> v[VMAX];
vector<pair<int,int>> opt;
int dist[VMAX];
int n;

void dijkstras1(int start){
  priority_queue<pair<int,int>> pq;
  for(int i=0; i<=n; i++) dist[i] = INF;
  dist[1]=0;
  pq.push({-0, 1});
  while(!pq.empty()){
    int x = pq.top().second;
    int wx = -pq.top().first;
    pq.pop();
    if(x==n) return ;
    for(int i=0; i<v[x].size(); i++){
      int y = v[x][i].first;
      int wy = v[x][i].second;
      if(dist[y] > dist[x] + wy){
        dist[y] = dist[x] + wy;
        pq.push({-dist[y], y});
        opt.push_back({x,y});
      }
    }
  }
}

void dijkstras2(int start, pair<int,int> a){
  int tx = a.first;
  int ty = a.second;
  priority_queue<pair<int,int>> pq;
  for(int i=0; i<=n; i++) dist[i] = INF;
  dist[1]=0;
  pq.push({-0, 1});
  while(!pq.empty()){
    int x = pq.top().second;
    int wx = -pq.top().first;
    pq.pop();
    if(x==n) return ;
    for(int i=0; i<v[x].size(); i++){
      int y = v[x][i].first;
      int wy = v[x][i].second;
      if(!(y==ty && x==tx) && !(y==tx && x==ty) && dist[y] > dist[x] + wy){
        dist[y] = dist[x] + wy;
        pq.push({-dist[y], y});
      }
    }
  }
}

int main(){
  int m; cin >> n >> m;
  int result=0;
  for(int x,y,w,i=0; i<m; i++){
    scanf("%d %d %d", &x, &y, &w);
    v[x].push_back({y,w});
    v[y].push_back({x,w});
  }
  dijkstras1(1);
  if(dist[n]==INF){
    printf("0");
    return 0;
  }
  int minv = dist[n];

  for(int i=0; i<opt.size(); i++){
    dijkstras2(1, opt[i]);
    if(dist[n]==INF){
      printf("-1");
      return 0;
    }else{
      result = max(result, dist[n] - minv);
    }
  }
  printf("%d", result);
}

느낀점

첫 접근때, 최단경로에 해당하는 도로만을 모아서 하나씩 검문하는 것이 불가능하다고 생각했다. 그래서 모든 도로에 대해 각 도로를 검문하도록 했더니 시간초과가 나왔다. 어떻게 최적화 시킬 수 있을까 하고 고민하다가 1->n으로의 최단경로를 이루는 도로들만을 구하는 것은 어렵겠지만 최단경로를 탐색하는 과정에서 거친 도로들을 모으면 이전보다 최적화될것이라고 생각하고 코드를 짰더니 통과가 되었다. 나름의 고민끝에 이전보다 더 코드를 짜 너무 뿌듯했다.

 

-> 지금 생각해보니,, routing algorithm처럼 각 노드에서 연결된 노드들을 저장시켜서 꼬리물기 방식으로 탐색하면 1->n으로 향하는 최단 경로를 구할 수 있다!