[백준 20955번] [Kotlin] 민서의 응급 수술

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

20955번: 민서의 응급 수술

 

난이도 : 골드 4
태그 : 자료구조, 그래프 이론, 분리집합, 트리

 

 

설명

각 뉴런은 시냅스로 연결됩니다. 뉴런은 노드(Node) 혹은 정점(Vertex), 시냅스는 간선(Edge)로 볼 수 있겠습니다.

모든 뉴런이 시냅스로 연결되면서 사이클이 없어야 하는 트리(사이클이 없는 연결 그래프) 구조여야 합니다.

 

사이클이 생기지 않으면서, 각 노드를 간선으로 병합하는 과정에서는 분리집합 - 유니온파인드가 유용하게 쓰일 것 같네요.

잘 모르시겠다면 아래 포스트를 참고해주세요.

https://uknowblog.tistory.com/61

[자료구조] 분리 집합(Disjoint set)과 유니온 - 파인드(Union-Find)

 

 

분리집합과 유니온파인드를 간단히 설명해보자면,

 

위와 같이 두 트리 구조가 있을 때,

 

 

특정 노드 x에서 최상위 노드(루트)를 찾는게 find 작업,

 

 

어느 한쪽 트리의 루트를 다른 트리의 루트의 자식노드로 포함시키는 작업이 union 작업입니다.

 

즉, 여러 개의 트리가 있을 때,

find로 각 트리의 부모를 찾고, 두 트리의 노드를 같게 만들어주는 작업이 union 작업입니다.

 

해당 문제 같은 경우엔 union 작업을 수행하며, union 작업이 몇 번 수행되었는지 카운팅하면 되겠죠?

아니네요 ㅠㅠ;

무엇이 잘못되었는지 곰곰히 생각하다가, 문제의 지문을 다시 읽으며 뭘 빠뜨렸는지 꼼꼼히 읽어봤습니다.

 

 

'이미 연결된 두 뉴런의 연결을 끊는다.' ?

그렇습니다.

입력이 처음 주어질 때 부터 이미 사이클이 형성되어 있는 경우도 있는 것입니다.

따라서 이 사이클이 형성되어 있다면 끊어주는 작업이 필요한 것입니다.

다만, 문제에서는 몇 번의 작업을 해야하는지 출력하는게 목적이므로,

실제로 사이클을 끊어주는 작업을 할 필요는 없고, 그냥 사이클의 개수를 카운팅하기만 하면 됩니다.

 

 

 

소스코드

package baekjoon.gold.g4.민서의응급수술

import java.util.StringTokenizer

lateinit var parent: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    parent = Array(n + 1) { it }

    var cnt = 0

    repeat(m) {
        val st = StringTokenizer(readLine())
        // 사이클이 발생되었다면 이를 끊어줘야 함
        if(!union(st.nextToken().toInt(), st.nextToken().toInt())) cnt++
    }

    for (i in 2..n) {
        // 두 노드가 다른 집합에 있다면 같은 집합으로 병합(union) 후 true 반환
        if (union(1, i)) cnt++
    }

    println(cnt)
}

fun find(x: Int): Int {
    return if (parent[x] == x) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

fun union(x: Int, y: Int): Boolean {
    val nx = find(x)
    val ny = find(y)

    return if (nx != ny) {
        parent[ny] = nx
        true
    } else false
}

 

-parant 배열

parent 배열은 각 노드의 부모를 저장하고 있는 배열입니다. 루트가 아닌 부모 노드입니다.

 

- find(x): Int 

find는 부모 노드를 찾는 메서드로, 내부적으로 재귀적으로 호출되어 최종적으로 x의 최상위 노드를 찾습니다.

 

- union(x, y): Boolean

union은 내부적으로 find를 수행하여 x, y 각각의 부모를 찾고,

두 노드의 루트가 같다면 (=같은 집합 이라면) false 를 반환합니다.

두 노드의 루트가 다르다면 (=다른 집합 이라면) 루트를 같게 만들어주고 true를 반환합니다.

 

- 간선 입력

    repeat(m) {
        val st = StringTokenizer(readLine())
        // 사이클이 발생되었다면 이를 끊어줘야 함
        if(!union(st.nextToken().toInt(), st.nextToken().toInt())) cnt++
    }

간선을 입력받으면서 union 작업을 이용해 미리 연결되어 있는 노드들을 이어줍니다.

이 때, 노드가 이미 연결되어있을 경우 사이클이 발생된 것이므로, 사이클을 끊어주는 의미로 cnt를 1 증가시킵니다.

 

- 모든 노드를 이어주기

    for (i in 2..n) {
        // 두 노드가 다른 집합에 있다면 같은 집합으로 병합(union) 후 true 반환
        if (union(1, i)) cnt++
    }

 

이제 모든 노드를 서로 이어줘야(같은 집합으로 만듬) 합니다.

그냥 단순히, 1번 노드와 2~n번 노드를 이어주면 되겠죠?

union 작업이 성공하면(true) cnt를 1 증가시킵니다.

 

 

 

후기

미리 연결된 간선들이 사이클이 있을 수 있어 끊어줘야 한다는 생각을 하지 못해 고심했던 문제였습니다.

분리집합과 유니온파인드를 연습하기 좋은 문제였던 것 같네요.