백준 [1976] kotlin

[문제]

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

1976번: 여행 가자

[풀이]

문제 푸는 과정은 2가지로 크게 나뉜다.

1. union-find를 이용하여, 경로 정보를 입력받아 spanning tree를 만든다.

2. spanning tree의 부모를 체크하여, 여행 경로가 같은 경로상에 존재하는지 확인한다.

 

<과정1>

입력받은 도시의 길을 기반으로 spanning tree를 만들기 위해 union-find를 사용했다.

 

<과정2>

spanning tree를 만들었으면 여행 경로가 정상적으로 짜였는지 확인을 한다.

여행 일정에서 a에서 b로 이동할 때마다, a와 b의 부모가 연결되어 있는지 체크를 한다.

문제에서 다른 경로를 경유해도 상관 없다고 했으므로,

부모가 같다면, 두 여행지는 같은 경로상에 존재함을 알 수 있다.

만약 다르다면, 두 여행지는 같은 경로상에 존재하지 않아 여행이 불가능해 "NO"를 출력하고 종료하면 된다.

부모가 다른 경우가 생기지 않고 최종 목적지까지 도착하면, "YES"를 출력해준다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

lateinit var parent : IntArray
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var N = br.readLine().toInt()
    var M = br.readLine().toInt()

    parent = IntArray(N,{it})
    repeat(N)
    {
        i ->
        val tmp = br.readLine().split(" ").map { it.toInt() }
        for(j in tmp.indices)
        {
            if(tmp[j] == 0) continue
            if(getParent(i) == getParent(j)) continue
            union(i,j)
        }
    }
    val tmp = br.readLine().split(" ").map { it.toInt() }
    for(i in 0 until tmp.size-1)
    {
        if(getParent(tmp[i]-1) != getParent(tmp[i+1]-1)){
            bw.write("NO")
            bw.flush()
            bw.close()
            return
        }
    }
    bw.write("YES")
    bw.flush()
    bw.close()
}

fun getParent(x : Int) : Int
{
    if(parent[x] == x) return x
    parent[x] = getParent(parent[x])
    return parent[x]
}
fun union(x: Int, y : Int)
{
    val x = getParent(x)
    val y = getParent(y)
    if(x>=y) parent[x] = y;
    else parent[y] = x;
}