[백준 1976번] [Kotlin] 여행 가자

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

1976번: 여행 가자

 

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

 

 

설명

이미 갔던 도시를 또 다시 방문 및 경유하여 다른 도시로 가도 되므로,

가려고 하는 도시끼리 모두 이어져있는지 (같은 그룹에 있는지) 판단하면 될 것 같습니다.

이 문제에는 분리집합 알고리즘이 유용하게 쓰일 것 같네요.

 

분리집합 알고리즘을 모르신다면 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/61

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

 

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

lateinit var connected: Array<Array<Boolean>>
lateinit var parent: Array<Int>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val n = br.readLine().toInt()
    val m = br.readLine().toInt()

    connected = Array(n) { Array(n) { false } }

    parent = Array(n) { it }

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine())
        repeat(n) { y ->
            connected[x][y] = st.nextToken().toInt() == 1
        }
    }

    repeat(n) { x ->
        repeat(n) { y ->
            if (connected[x][y]) {
                if (find(x) != find(y)) {
                    union(x, y)
                }
            }
        }
    }

    val st = StringTokenizer(br.readLine())
    val target = Array(m) { 0 }
    repeat(m) {
        target[it] = st.nextToken().toInt() - 1
    }

    val firstParent = find(target[0])

    for(i in 1 until  m) {
        if(firstParent != find(target[i])) {
            println("NO")
            return
        }
    }
    println("YES")

}

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

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

    if (nx != ny) {
        parent[ny] = nx
    }
}

 

union(x, y) 까지는 연결되어 있는 모든 도시끼리 같은 그룹으로 만들어 주는 부분이고,

 

val firstParent = find(target[0])

for(i in 1 until  m) {
    if(firstParent != find(target[i])) {
        println("NO")
        return
    }
}

 

해당 부분은 모든 도시가 부모가 같은지 판단하는 부분입니다.

같은 그룹끼리는 최상위 노드(루트)가 모두 같은 노드를 가르키고 있으므로,

다른 노드들과 루트가 다른 노드가 있다면, 이 루트(도시)는 다른 그룹에 속해있으며, 갈 수 없는 도시입니다.

 

따라서 하나라도 루트가 다른 노드가 있다면, NO 를 출력합니다.

 

 

 

후기

분리집합 알고리즘을 연습하기 좋은 문제인 것 같습니다.