백준 1043번 거짓말 - 스위프트(Swift) 풀이

1. 같은 파티에 참석하는 사람들끼리는 같은 종류(진실/거짓)를 들어야 하므로 한 집합으로 묶는다.
2. 진실을 아는 사람들을 한 집합으로 묶는다.
3. 각 파티의 참석자들이 진실을 알아야 하는 집단인지 체크한다.

---

1. 같은 파티에 참석하는 사람들끼리는 같은 종류(진실/거짓)를 들어야 하므로 한 집합으로 묶는다.

 같은 종류를 들어야 하는 사람들을 한 집합으로 묶어 취급할 것이다. Union-Find 알고리즘을 사용해서 구현하면 된다. 같은 파티에 참석하는 사람들은 무조건 같은 종류를 들어야 한다. 따라서 한 파티 내의 참석자들을 한 집합으로 묶는다.

 

2. 진실을 아는 사람들을 한 집합으로 묶는다.

 이제 진실을 아는 사람들도 모두 진실을 들어야 하므로 한 집합으로 묶어준다. 이렇게 되면 만약 파티 참석자 중에 진실을 들어야 하는 사람이 한 사람이라도 있으면, 나머지 참석자들도 모두 진실을 들어야 하는 집합으로 같이 묶이게 된다.

 

3. 각 파티의 참석자들이 진실을 알아야하는 집단인지 체크한다.

 한 파티에 참석자들을 모두 한 집합으로 묶어주었으므로, 참석자 중 아무나 한 명을 골라 진실을 들어야 하는 집합에 속하는지 확인(find)하면 된다.

 

---

import Foundation

var parties = [[Int]]()
var parent = [Int]()
var size = [Int]()
var N = 0, M = 0

func initUnionFind(n: Int) {
    parent = (0...n).map{ $0 }
    size = Array(repeating: 1, count: n + 1)
}

func find(_ x: Int) -> Int {
    if parent[x] == x { return x }
    
    parent[x] = find(parent[x])
    
    return parent[x]
}

func union(a: Int, b: Int) {
    var pa = find(a), pb = find(b)
    
    guard pa != pb else { return }
    
    if size[pa] < size[pb] { swap(&pa, &pb) }
    parent[pb] = pa
    size[pa] += size[pb]
}

func solution() -> String {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    initUnionFind(n: N)
    
    let whoKnowsTruth = Array(readLine()!.split(separator: " ").map{ Int(String($0))! }.dropFirst())
    
    for _ in 0..<M {
        let participants = Array(readLine()!.split(separator: " ").map{ Int(String($0))! }.dropFirst())
        parties.append(participants)
    }
    
    for party in parties {                      // 같은 파티에 참석하는 사람들끼리는 같은 종류를 들어야함
        for i in 0..<party.count-1 {
            union(a: party[i], b: party[i+1])
        }
    }
    
    var result = 0
    
    if !whoKnowsTruth.isEmpty {
        for i in 0..<whoKnowsTruth.count-1 {    // 진실을 아는 사람을 하나로 묶어줌
            union(a: whoKnowsTruth[i], b: whoKnowsTruth[i+1])
        }
        
        for party in parties {                  // 각 파티의 참석자들이 진실을 알아야하는 집단인지 체크
            if find(party.first!) != find(whoKnowsTruth.first!) {
                result += 1
            }
        }
    } else {
        result = M
    }
    
    return "\(result)"
}

print(solution())