[백준 11562번] 백양로 브레이크 (C++)

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

11562번: 백양로 브레이크

서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공

www.acmicpc.net

~~백양로 브레이크 문제~~는 ~~플로이드 알고리즘~~을 이용하여 해결할 수 있습니다.

최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력해야합니다.

모든 길을 양방향으로 바꾸더라도 서로 도달 불가능한 건물이 없는 입력만 주어지므로,

아래와 같은 알고리즘을 생각해볼 수 있습니다.

입력 받은 각 길이 일방통행인지, 양방향인지 기록해둔다.
모든 길을 길이가 1인 양방향 길로 바꾼 후, 플로이드 알고리즘을 수행하여 모든 건물 간의 최단 거리를 계산한다.
아래 과정을 k번 수행한다.
1. s, e를 입력 받는다.
2. s, e간의 최단 경로를 추척하여 경로에서 원래 일방통행이었던 길을 만날 때마다 cnt를 증가시켜준다.
3. cnt를 출력한다.

하지만, 위의 알고리즘의 경우 s에서 e로의 경로가 2가지 이상일 경우, 양방향으로 바꾸지 않아도 e에 도달할 수 있음에도 간선의 개수가 더 적은 경로를 최단 거리로 인식하여, 방향을 바꿔야 e에 도달할 수 있는 경로가 최단 거리가 될 수 있습니다.

아래의 테스트케이스의 경우, 1에서 4로 갈 때, 1-2-3-4의 경로로 가면 방향을 바꾸지 않아도 되지만, 1-2-4의 경로로 가면 2->4의 길의 방향을 바꿔주어야 합니다.

따라서, 기존에 없던 방향의 비용을 높게 설정하여, 최대한 기존 방향을 선택하되, e에 도달할 수 없으면 일방통행을 양방향으로 바꾸도록 해야합니다.

아래는 전체 코드입니다.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

#define SIZE 251
#define INF 10000000

int dist[SIZE][SIZE];   // dist[u][v]는 u와 v 사이의 최단 거리
int nxt[SIZE][SIZE];    // nxt[u][v]는 u에서 v간의 최단 경로에서, u 다음 정점의 번호
bool conn[SIZE][SIZE]; // conn[u][v]는 u와 v 사이에 간선이 존재하는지 나타냄

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, b; cin >> u >> v >> b;
        conn[u][v] = true;
        if(b == 1) conn[v][u] = true;  // 영방향인 경우
    }

    fill(&dist[0][0], &dist[SIZE - 1][SIZE], INF);  // 최단 거리 배열을 INF로 설정
    for(int i = 1; i <= n; i++) conn[i][i] = true;  // 동일한 정점간의 간선이 존재한다고 설정
    for(int i = 1; i <= n; i++) dist[i][i] = 0; // 동일한 정점간의 거리는 0
    for(int i = 1; i <= n; i++) nxt[i][i] = i;  // u에서 u로 이동할 때, u 다음 정점은 u

    for(int u = 1; u <= n; u++){    // 각 간선을 양방향으로 수정하고, 기존에 없던 방향의 비용을 높게 설정해줌
        for(int v = 1; v <= n; v++){
            if(conn[u][v] == true){ // 존재하는 간선인 경우
                nxt[u][v] = v; nxt[v][u] = u;
                dist[u][v] = 1; // 간선의 비용을 1로 설정
                if(conn[v][u] == true) dist[v][u] = 1; // 양방향인 경우
                else dist[v][u] = 500;  // 기존에 없던 방향의 비용을 높게 설정
            }
        }
    }

    for(int pass = 1; pass <= n; pass++){   // 플로이드 알고리즘 수행
        for(int st = 1; st <= n; st++){
            for(int en = 1; en <= n; en++){
                int d = dist[st][pass] + dist[pass][en];
                if(dist[st][en] > d) {
                    dist[st][en] = d;
                    nxt[st][en] = nxt[st][pass];
                }
            }
        }
    }

    cin >> k;
    while(k--){
        int s, e; cin >> s >> e;
        int cnt = 0;    // 일방통행인 길을 양방향 통행으로 바꿔야할 길의 개수
        int pr = s; // s에서 e로의 경로상에서 이전 정점
        int nx = nxt[s][e]; // 다음 정점
        while(nx != e){ // nx가 도착 지점이 될 때까지 반복
            if(conn[pr][nx] != true) cnt++; // 기존에 없던 방향인 경우 cnt 증가
            pr = nx;
            nx = nxt[nx][e];
        }
        if(conn[pr][nx] != true) cnt++; // 기존에 없던 방향인 경우 cnt 증가
        cout << cnt << "\n";
    }
}

아래는 문제 풀이에 사용된 테스트케이스입니다.

4 3
1 2 1
2 3 1
3 4 1
7
1 1
1 2
2 1
1 4
4 1
2 3
4 3
-> 0 0 0 0 0 0 0

4 3
1 2 0
2 3 1
3 4 0
5
1 1
2 2
3 3
4 4
4 3
-> 0 0 0 0 1

4 4
1 2 0
2 3 1
3 4 1
4 2 0
1
1 4
 -> 0

티스토리툴바