백준 1976 여행가자

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

분류: 자료구조, 분리 집합

---

접근방식

서로소 집합 문제였습니다.

https://woongsios.tistory.com/200 와 같은 방식으로 해결했습니다.

연결되어 있는지만 확인하면 되기 때문에 같은 집합은 하나의 root로 바꿔주고 root가 같은지만 확인하면 되는 문제였습니다!

 

해결방법

import Foundation

let n = Int(readLine()!)!
let m = Int(readLine()!)!
var cities = [Int](0..<n)

func root(of n: Int) -> Int {
    guard cities[n] != n else { return n }
    cities[n] = root(of: cities[n])
    return cities[n]
}

func union(_ a: Int, _ b: Int) {
    let rootA = root(of: a)
    let rootB = root(of: b)
    if rootA < rootB {
        cities[rootB] = rootA
    } else if rootB < rootA {
        cities[rootA] = rootB
    }
}

for i in 0..<n {
    let connects = readLine()!.split(separator: " ").map { Int(String($0))! }
    for j in i+1..<n {
        guard connects[j] == 1 else { continue }
        union(i, j)
    }
}

func checkResult() {
    let route = readLine()!.split(separator: " ").map { Int(String($0))!-1 }
    let adj = root(of: route[0])
    for i in 1..<route.count {
        guard root(of: route[i]) != adj else { continue }
        print("NO")
        return
    }
    print("YES")
    return
}

checkResult()