[백준] 2325 개코전쟁, 2307 도로검문 (C++)

99% 똑같은 문제다.
이 글은 2325 개코전쟁을 기준으로 서술하였다.

문제를 풀고, 글을 읽으면 좋을 것 같다.

2325번: 개코전쟁

 

2307번: 도로검문

문제를 요약해보자.
1번 -> N번으로 가는 최단거리가 최대가 되도록 길을 하나 없애야 한다. 그런 식으로 길을 하나 없앤 후, 최단거리는?

---

문제를 읽어보면 다음 사실을 쉽게 알 수 있다.
길 하나를 끊을 때, 최단 경로 중에서 하나를 끊어야 최단거리가 최대가 된다.
최단경로가 아닌 경로에서 길을 끊어봤자 최단경로가 변하지 않기 때문이다.
그러니까 최단 경로에서 길을 끊어야 한다.


그렇다면 풀이는 다음과 같이 요약할 수 있다.
1. 우선 길을 끊기 전의 최단거리 및 최단경로를 구한다. (다익스트라로)
2. 구한 최단 경로 내의 모든 간선을 한 번씩 끊어보면서 최단거리를 다시 구한다.
3. 2의 과정에서 구한 최단거리 중 최댓값이 답이 된다.

위 풀이대로 풀었고, 맞았다. 코드는 아래와 같다.

코드

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
#define INF 9876543210
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

bool chk = true;   //chk가 true면 첫 다익스트라
ll n, m, a, b, t;
ll dis[1001];
ll before[1001];
ll x = -1, y = -1; //지우고 싶은 간선
vector<pll> adj[1001];

void dijkstra(ll S) {
    fill(dis, dis + 1001, INF);
    priority_queue<pll> pq;
    dis[S] = 0;
    pq.push({ 0,S });
    while (!pq.empty()) {
        ll d = -pq.top().first;
        ll u = pq.top().second;
        pq.pop();
        if (d > dis[u]) continue;
        for (ll i = 0; i < adj[u].size(); i++) {
            ll v = adj[u][i].first;
            ll c = adj[u][i].second;
            if ((u == x && v == y) || (u == y && v == x)) continue;
            if (dis[v] > dis[u] + c) {
                if(chk) before[v] = u; //첫 다익스트라에서만 경로를 저장하자
                dis[v] = dis[u] + c;
                pq.push({ -dis[v],v });
            }
        }
    }
}

void solve() {
    memset(before, -1, sizeof(before));
	cin >> n >> m;
	for (ll i = 0; i < m; i++) {
		cin >> a >> b >> t;
		adj[a].push_back({ b,t });
		adj[b].push_back({ a,t });
	}
    dijkstra(1);
    chk = false;
    ll ans = 0;
    for (ll now = n; now != -1; now = before[now]) {
        x = before[now];
        y = now;
        dijkstra(1);
        ans = max(ans, dis[n]);
    }
    cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
	return 0;
}

---

아니 그런데 갑자기 이런 생각이 들었다.
최단 경로가 여러개라면 어떡하지...
내가 찾은 최단경로에서 답이 나오는 게 항상 보장되나?

우선 정답은 "그렇다"이다.

혼자 고민하다가 증명이 쉽지 않아서 swoon님께 질문을 했는데, 이해하기 쉽게 설명해주셨다.
이거 때문에 글을 쓴다!

---

1. 최단 경로가 유일할 경우

유일한 최단 경로에서 길을 끊어야 최단거리가 커지는 것을 쉽게 알 수 있다. (최단 경로가 아닌 경로에서 자르면 최단경로가 그대로 유지되므로)

즉, 우리가 찾은 최단경로에서 답이 나온다.

2. 최단 경로가 여러개인 경우

이 부분이 중요하다.
두 경우로 나누어 보자.

(i) 하나도 겹치지 않는 최단경로가 있는 경우
아래와 같은 그래프를 보자. 아래 그래프에서 모든 경우를 다 설명할 수 있을 것 같아서 한 번 그려보았다.
시작점을 S, 도착점을 T라고 하자.

빨강, 주황, 연두, 파랑색으로 칠한 경로가 최단거리임을 쉽게 알 수 있다.

위 그림에서 겹치는 최단경로는 하나의 최단경로라고 생각해보자.
그럼 총 3개(빨+주, 연두, 파랑)의 최단경로가 있다.
3개의 최단경로 중 어디에서 간선을 끊어도 다른 최단경로가 그대로 유지된다.
그러므로 어떤 최단경로 위의 간선을 끊어도 답은 항상 동일하다. (끊기 전 최단거리와 동일)

따라서 이 경우에 우리가 찾은 최단경로 위에서 답이 나옴이 보장된다. (어떤 최단경로를 찾아도 답은 항상 기존의 최단거리이므로)


(ii) 최단경로가 겹치는 경우

이 경우 최단경로위의 간선은 아래의 두 집합 중 하나에 속해있다.
(a) 하나의 최단경로 위의 간선인 경우 ( S->1, 1->2, S->3, 3->2 )
(b) 여러 최단경로 위의 간선인 경우 ( 2->T )

(a)에서는 답이 나올 수 없음을 보여서 답은 항상 (b)에서 나옴을 증명할 수 있다.

(a) 하나의 최단경로 위의 간선인 경우
이 때는 간선을 지워도 다른 최단경로는 그대로 유지되기 때문에 지울 이유가 없다. 그러니까 오직 하나의 최단경로에만 속하는 간선은 지울 이유가 없다. 이것도 사실 (1. 최단경로가 유일한 경우)와 다를 게 없다.

그러니까 최단경로가 여러개인 경우엔 항상 모든 최단경로에 속해있는 간선(위 그림에서는 2->T)에서 답이 나온다.
즉, 우리가 찾은 최단경로에도 그 간선이 무조건 존재한다.

따라서 이 경우에도 우리가 찾은 최단경로에서 답이 나옴이 보장된다.

---

증명(?)되었다!



나는 이해가 되었는데, 누군가가 이해할 수 있을지 잘 모르겠다.
내 글솜씨가 매우 처참한 것을 다시한 번 느끼게 해주는 포스팅이다. ㅠ


ps) 개코전쟁은 P5, 도로검문은 G2인데 이유를 잘 모르겠다. 개인적으로 둘 다 같은 난이도라고 생각. 위의 증명이 생각하기 쉽지 않아서 P5가 적당한 것 같다.

ps2) 개코전쟁을 풀어서 플래티넘2로 승급했다!!

solved.ac 레이팅이 의미없는 걸 잘 알지만 기분이 매우 좋다!