백준 11562 백양로 브레이크 Kotlin (플로이드 와샬)

문제 출처 : https://www.acmicpc.net/problem/11562

11562번: 백양로 브레이크

문제

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

컴퓨터과학과 학생 남규는 전공 수업을 듣고 교양 수업을 들으러 가던 중 길을 잃어 3일 밤낮을 헤매다가 공학관에서 종합관으로 가는 길은 존재하지 않는다는 결론을 내렸다.

3일 사이에 과제도 내지 못하고 출석도 하지 못해 학사경고 위기에 처한 남규는 전공을 살려 현재 일방통행인 길들 중 반드시 양방향으로 바꿔야만 하는 길이 몇 개인지 조사해 학교에 건의하기로 마음을 먹었다.

남규는 여러 건물들 사이를 직접 잇는 길들을 모두 조사했고, 그 중 어떤 길들이 일방통행인지, 또는 양방향 통행이 가능한지를 모두 체크했다.

남규의 프로그램은 간단하다. 출발지와 도착지를 입력하면 도착지까지 가기 위해 최소 몇 개의 길을 양방향으로 바꿔야만 하는지를 출력해준다. 프로그램이 완성되었다는 소문이 퍼지자, 남규처럼 길을 잃고 헤맨 경험이 있는 학생들은 남규에게 묻기 시작했다.

"공학관에서 대강당 갈 수 있어?"

"상경대 별관에서 학관으로는?"

남규는 매번 손으로 타이핑해 입력하고 결과를 보내주는 데에 지치고 말았다.

결국 앓아누운 남규를 위해 학생들의 질문을 해결할 새로운 프로그램을 만들어보자.

입력

첫 줄에 Y대학교 건물의 수 n과 길의 수 m이 주어진다. (n ≤ 250, m ≤ n * (n - 1) / 2 )

다음 m줄에 걸쳐, u v b (1 ≤ u ≤ n, 1 ≤ v ≤ n, u != v, b = 0 또는 1) 의 형태로 길에 대한 정보가 주어진다.

b가 0일 경우 u에서 v로 가는 일방통행 길인 것이고, b가 1일 경우 u와 v를 잇는 양방향 길이다.

어떤 두 건물 사이를 잇는 길은 최대 한 개이다.

다음 줄에 학생들의 질문의 수 k가 주어진다. (1 ≤ k ≤ 30,000)

다음 k줄에 걸쳐 s e (1 ≤ s ≤ n, 1 ≤ e ≤ n)의 형태로 학생들의 질문들이 주어진다.

이는 질문한 학생이 건물 s에서 건물 e로 가고 싶다는 의미이다.

출력

출력은 k줄에 걸쳐 이루어진다.

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

모든 길을 양방향으로 바꾸더라도 서로 도달 불가능한 건물은 없다.

알고리즘 분류

• 그래프 이론
• 플로이드–워셜

풀이

오랜만에 플로이드 와샬 문제~!

플로이드 와샬이나 다익스트라는 가중치가 있는 상황에서 최단 경로를 구할 때 사용한다.

여기서 다익스트라는 시작 지점과 목표 지점이 한 개인 경우에 주로 사용되고, 플로이드 와샬은 시작 지점과 목표 지점이 여러 개인 경우 사용하기 좋다.

해당 문제는 여러 시작 지점에서 여러 목표 지점으로 가는 데에 최단 경로를 요구하고 있으므로 플로이드 와샬로 풀었다.

O(250^3)으로 무리 없이 통과할 수 있다.

또 다른 점은 '간선을 몇 번 타는지'등의 일반적인 최단 경로가 아니라 's -> e로 가는 데에 양방향 간선을 몇 개 만들어야 하는지'가 최단 경로의 조건이다.

우선 2차원 dp를 s == e인 경우는 시작점과 도착 지점이 같은 경우로 0으로 초기화하고 나머지는 INF값으로 초기화한다.

이후에 간선 정보를 입력받아 단방향 간선인 경우 dp[s][e] = 0을 저장하고, 이 s,e는 단방향에서 양방향 간선으로 바꿀 수 있다는 의미로 dp[e][s] = 1을 저장한다. 이는 곧, 양방향 간선을 만드는 횟수가 된다.

양방향 간선인 경우 dp[s][e] = 0, dp[e][s] =0 을 저장한다.

이후에 플로이드 와샬로 s에서 특정 지점 x를 거쳐 e로 도달하는 데에 양방향 간선을 만드는 횟수를 최소로 갱신해 가면 된다.

이후엔 학생들의 질문 수 K를 입력받아 K만큼의 dp[s][e]를 출력하면 된다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m) = getIntList()
    val dp = Array(n+1){ r->
        IntArray(n+1){c->
            if(r == c) 0 else 987654321
        }
    }
    repeat(m){
        val (s,e,v) = getIntList()
        dp[s][e] = 0
        if(v == 1){
            dp[e][s] = 0
        }else{
            dp[e][s] = 1
        }
    }
    //solve
    for(k in 1 .. n){
        for(i in 1 .. n){
            for(j in 1 .. n){
                dp[i][j] = dp[i][j].coerceAtMost(dp[i][k] + dp[k][j])
            }
        }
    }
    repeat(getInt()){
        val (s,e) = getIntList()
        //output
        write("${dp[s][e]}\n")
    }
    close()
}