백준 24391번: 귀찮은 해강이

문제: https://www.acmicpc.net/problem/24391

문제 풀이

Union Find

root[i] = i번 건물과 연결된 건물 중 가장 번호가 빠른 번호

find(x) = x번 건물과 연결된 건물 중 가장 번호가 빠른 번호를 찾는 재귀 함수

union(x, y) = x번 건물과 y번 건물을 연결하는 함수

prev = 현재 수강한 강의의 번호

cur = 수강하러 가야하는 강의의 번호

count = 밖으로 나가야 하는 횟수

처음엔 건물이 연결되어있지 않으므로 root 배열을 본인 건물의 번호로 초기화함

연결해야 하는 두 건물의 번호가 주어지면 union(x, y) 함수를 이용해 두 건물을 연결함

강의 순서를 입력받으면 첫 강의를 듣고 다음 강의를 들으러 밖으로 나가야 하는지 확인해야 하므로 첫 강의를 prev에 저장하고 다음 강의부터 cur에 입력받음

find(prev), find(cur)가 같은지 확인해 같지 않으면 건물이 연결되지 않은 것이므로 count를 1 증가시킴

cur에 저장된 번호의 강의를 수강하러 이동한 것이므로 prev에 cur에 저장된 번호를 대입하고 다음 강의의 번호를 cur에 입력받음

이 과정을 모든 강의 순서대로 입력받으면 count에 밖으로 나가야 하는 횟수가 저장되어있으므로 출력하면 정답

풀이 설명

해강이는 앙중대학교에 다닌다. 해강이는 이번 학기에 강의코드 1번부터 N번까지 N개의 강의를 듣고 있다.

모든 강의는 강의코드와 동일한 번호의 건물에서 진행된다. 예를 들어, 강의코드가 1인 강의는 1번 건물에서 진행되고, 강의코드가 N-1인 강의는 N-1번 건물에서 진행된다.

해강이는 밖에 나오는 것을 싫어해서, 강의 시간표 순서대로 모든 강의를 들으면서 한 건물에서 밖으로 나와서 다른 건물로 이동하는 횟수를 최소화하고 싶다. 앙중대학교에는 다행히도 서로 연결되어 있는 건물들이 있어, 이 건물끼리는 밖으로 나오지 않고 이동할 수 있다.

해강이의 강의 시간표가 주어질 때, 밖에 나오는 것을 싫어하는 해강이를 위해 최소 몇 번만 밖에 나오면 되는지 구해보자. 맨 처음 강의를 들으러 이동하는 횟수는 세지 않는다.

강의가 순서대로 진행된다고 했으므로 다음 강의를 들으러 갈 때 밖으로 나가야 하는 경우는 현재 들었던 강의의 건물과 다음 강의의 건물이 연결되지 않은 경우이다. 따라서 두 건물이 연결되어있는지 확인하는 방법이 필요하다.

Union Find를 이용해 그 건물과 연결되어 있는 건물 중 번호가 가장 빠른 건물을 저장해 놓는다면 두 건물이 연결되어있는지 여부를 빠르게 구할 수 있다. 따라서 연결된 건물 중 가장 빠른 번호를 저장하기 위해 root 배열을 만든다.

건물을 연결하다 보면 배열의 값에 저장된 건물이 더 빠른 번호의 건물이 연결되어 실제 상황과 맞지 않는 번호가 저장될 때가 있다. 그러므로 배열의 값을 확인할 때 바로 사용하는 것이 아닌 그 번호의 건물이 더 빠른 번호의 건물과 연결되었는지 확인하기 위해 재귀적으로 root 배열의 값과 인덱스가 같을 때까지 번호를 찾아서 값을 대입해놓아야 한다. 이를 자주 사용하기 때문에 find(x) 함수로 따로 만들어놓는다.

두 건물을 연결할때에도 root 배열의 값을 직접 사용하지 않고 find(x) 함수를 사용해 가장 빠른 번호를 찾아놓고 더 빠른 번호를 root 배열에 저장해야 한다. 따라서 두 번호의 가장 빠른 번호를 find(x) 함수로 찾아서 더 큰 번호의 건물의 root 배열에 더 작은 번호를 저장하는 함수 union(x, y)를 정의한다.

이렇게 정의한 union(x, y), find(x) 함수를 이용해 건물들을 연결해놓고 강의 순서대로 확인하기 위해 현재 수강한 강의의 번호를 prev, 다음에 수강하러 가야하는 강의의 번호를 cur로 정의한다. 첫 강의를 들으러 이동하는 횟수는 세지 않는다고 했으므로 첫 강의의 번호를 바로 prev에 저장하고 다음 강의부터 cur에 저장한다.

이렇게 cur에 저장된 강의실 번호와 prev에 저장된 강의실 번호가 연결되었는지 확인하기 위해 각각 find(x) 함수를 돌린 값을 비교해 같지 않다면 연결되지 않은 것이므로 밖으로 나가는 횟수 count를 1 증가시킨다. 이제 cur에 저장된 번호의 강의를 수강하러 이동한 것이므로 prev에 이 번호를 저장하고 다음 강의의 번호를 cur에 입력받는다.

이를 모든 강의를 입력받을 동안 확인하면 count에 밖으로 나가는 횟수가 저장되어 있으므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val M = nextInt()
    val root = IntArray(N + 1){it}
    fun find(x: Int): Int{
        if(root[x] != x) root[x] = find(root[x])
        return root[x]
    }
    fun union(x: Int, y:Int){
        val xFind = find(x)
        val yFind = find(y)
        if(xFind < yFind){
            root[yFind] = xFind
        } else {
            root[xFind] = yFind
        }
    }
    repeat(M){
        val i = nextInt()
        val j = nextInt()
        union(i, j)
    }
    var prev = nextInt()
    var count = 0
    repeat(N - 1){
        val cur = nextInt()
        if(find(prev) != find(cur)){
            count++
        }
        prev = cur
    }
    println(count)
}