BOJ-1043 거짓말 Swift

문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

내가 푼 풀이

접근방법: Union-Find

진실을 아는사람의 집합과 모르는사람의 집합을 분리하여, 파티마다 진실을 아는사람이 있다면 거짓말을 할 수 없다.

이를 서로소집합인 분리집합에서 Union-Find 연산을 이용한다.

파티에 진실을 모르는사람과 아는사람이 공존한다면, 진실을 모르는사람이 다음 파티에서는 진실을 안상태라 거짓말쟁이가 된다.

따라서 매 파티마다 진실을 모르는사람과 아는사람이 공존하지 않을때 까지, 진실을 몰랐던사람을 아는사람과 같은 집합에 넣는다(Union)

최종적으로 분리된 집합을 이용하여 파티에서 과장된 이야기 할 수 있는 수를 구하면 된다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]
let know = readLine()!.split(separator: " ").map{Int(String($0))!}
var parent = Array(repeating: 0, count: N+1)
var party = [[Int]]()
var count = 0

// 분리집합
for i in 1...N {
    parent[i] = i
}

// 분리집합끼리 연결한다.
func union(_ x: Int,_ y: Int) {
    let rootX = findd(x)
    let rootY = findd(y)
    
    parent[rootY] = rootX
}

// 해당 원소의 루트노드를 찾는다.
func findd(_ x: Int) -> Int {
    if parent[x] == x { return x}
    parent[x] = findd(parent[x])
    
    return parent[x]
}

// 진실을 아는사람이 있는경우 루트0으로 연결
if know[0] != 0 {
    for i in 1..<know.count {
        union(0, know[i])
    }
}

// party 수만큼 입력받기
for i in 0..<M {
    party.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

// 매 파티마다 진실을 아는인원과 모르는인원이 공존하지 않을때 까지 반복한다.
var find = true
while find {
    find = false
    var inLiar = false
    for i in 0..<party.count {
        var previous = -1
        for j in 1..<party[i].count {
            let root = findd(party[i][j])
            // 처음 사람이면 previos 초기화
            if previous == -1 {
                previous = root
                continue
            }
            // 그 다음인원이 진실을 알고, 이전인원이 모르는경우
            if (root != previous && root == 0 ){
                inLiar = true
                break
            }
            // 그 다음인원이 진실을 모르고, 이전인원이 아는 경우
            if (previous == 0 && root != 0 ) {
                inLiar = true
                break
            }
            previous = root
        }
        // 파티안에 진실을 아는사람과 모르는사람이 공존한다면 모두 진실을 아는사람으로 바꾼다.(Union)
        if inLiar {
            find = true
            for j in 1..<party[i].count {
                union(0, party[i][j])
            }
        }
        inLiar = false
    }
}

// 완전히 갱신된 파티에서 거짓말을 할 수 있는지 파악
for i in 0..<party.count {
    var liar = false
    for j in 1..<party[i].count {
        if findd(party[i][j]) == 0 {
            liar = true
            break
        }
    }
    if !liar { count += 1}
}

print(count)