백준 19538번 루머 - 스위프트(Swift) 풀이

---

 

1. 최초 유포자부터 시작해 BFS로 루머를 퍼트려나간다.
2. X번 사람이 새로 루머를 믿게 되면, X의 모든 주변인들에 대해 주변인카운트를 1 증가시켜준다.
3. 만약 주변인카운트가 주변인 수의 절반 이상이 되면 루머를 믿게 된 것이므로 큐에 넣는다(방문한다).

 

1. 최초 유포자부터 시작해 BFS로 루머를 퍼트려나간다.

 매분 주변인에게 루머를 퍼트리는 상황은 너비우선탐색 상황과 같다. 최초 유포자들을 모두 큐에 넣은 상태로 BFS를 시작한다. 앞으로 큐에는 루머를 믿는 사람들만 넣을 것이다.

 

2. X번 사람이 새로 루머를 믿게 되면, X의 모든 주변인들에 대해 주변인카운트를 1 증가시켜준다.

 주변인의 절반 이상이 루머를 믿을 때 루머를 믿게 되므로, 자신의 주변인 중 몇 명이 루머를 믿고 있는지를 기록해두어야 한다. 이것을 주변인카운트라고 하자. X가 새로 루머를 믿게 되면, X의 모든 주변인들은 루머를 믿는 주변인이 한 명 늘어난 것이므로 주변인카운트를 1 증가시켜주자.

 

3. 만약 주변인카운트가 주변인 수의 절반 이상이 되면 루머를 믿게 된 것이므로 큐에 넣는다(방문한다).

 만약 2번 과정의 결과로 주변인카운트가 주변인 수의 절반 이상이 되었다면 이제 그 사람도 루머를 믿는 사람이 된 것이다. 따라서 큐에 넣어준다. 큐가 빌 때까지 계속 pop하면서 주변인들에게 루머를 퍼트리는 행위를 반복해준다. 큐가 빌 때까지 한 번도 큐에 들어가지 못한 사람은 끝까지 루머를 믿지 않는 사람이므로 -1을 출력해주면 된다.

반응형

---

import Foundation

var N = 0, M = 0
var adjacents = Array(repeating: [Int](), count: 200_001)
var visit = Array(repeating: false, count: 200_001)
var adjCount = Array(repeating: 0, count: 200_001)
var date = Array(repeating: -1, count: 200_001)
var startPoints = [Int]()

struct Queue {
    var queue = [Int]()
    var front = 0
    
    var isEmpty: Bool {
        return front >= queue.count
    }
    
    mutating func insert(_ n: Int) {
        queue.append(n)
    }
    
    mutating func popFront() -> Int {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func BFS() {
    var queue = Queue()
    
    for s in startPoints {
        visit[s] = true
        queue.insert(s)
        date[s] = 0
    }

    while !queue.isEmpty {
        let current = queue.popFront()
        
        for adj in adjacents[current] {
            guard !visit[adj] else { continue }
            
            adjCount[adj] += 1
            
            if adjCount[adj] * 2 >= adjacents[adj].count {
                visit[adj] = true
                date[adj] = date[current] + 1
                queue.insert(adj)
            }
        }
    }
}

func solution() {
    N = Int(readLine()!)!
    for i in 1...N {
        adjacents[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }.dropLast()
    }
    
    M = Int(readLine()!)!
    startPoints = readLine()!.split(separator: " ").map{ Int(String($0))! }
    
    BFS()
    
    var resultString = ""
    for i in 1...N {
        resultString.write("\(date[i]) ")
    }
    print(resultString)
}

solution()