전염병

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 위 문제도 * 2 연산, / 3 연산 결과를 각각 노드라고 가정하면 BFS를 적용하여 문제를 해결할 수 있음
• K는 1이상 값이므로 / 3 연산 시 0이 나올 수 있기 때문에 0번 위치는 이미 방문했다고 처리를 해야 함
• * 2 연산 시 마을의 개수를 넘어가면 안되기 때문에 해당 예외처리도 필요함
• 위 조건을 만족하면서 인접한 노드를 방문할 때마다 count 값을 증가시켜 주고,
• 해당 count 값이 K번 마을부터 전염병이 퍼진 마을의 개수이므로 전체 마을의 수(N) - count를 통해 전염병이 퍼진 마을을 제외시켜 줌으로써 전염병이 퍼지지 않은 마을의 수를 구할 수 있음

5. 전체 코드

//MARK: - 전염병

//MARK: - Framework
import Foundation

//MARK: - Variable
var visited: [Bool] = []

//MARK: - Function
func bfs(_ N: Int, _ K: Int) -> Int {
    var count, mul, div: Int
    var queue: [Int] = []
    
    count = 0
    mul = 0
    div = 0
    queue.append(K)
    visited[K] = true
    visited[0] = true
    
    while !queue.isEmpty {
        let current: Int = queue.removeFirst()
        count += 1
        
        if current * 2 <= N {
            mul = current * 2
        }
        div = current / 3
        
        if !visited[mul] {
            visited[mul] = true
            queue.append(mul)
        }
        
        if !visited[div] {
            visited[div] = true
            queue.append(div)
        }
    }
    
    return count
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    let N: Int = input.map { Int($0) }[0] ?? 0
    let K: Int = input.map { Int($0) }[1] ?? 0
    var result: Int = 0
    visited = Array(repeating: false, count: N + 10)
    
    //MARK: - Process
    result = N - bfs(N, K)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.