이상한 계산기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 위 문제는 개인적으로 너비우선탐색을 사용해야겠다고 떠올리는게 힘들었던 문제
• 단순히 * 2 연산과 / 3 연산을 반복해서 진행하다보면 시간초과가 발생할 수 있음
• 또, * 2 연산 시 5자리 이상 넘어가는 것을 방지해주어야 함
• 위 조건을 만족하면서 현재 값에서 * 2 한 위치, / 3 한 위치를 각각의 노드로 보고 해당 위치에 대해
• BFS를 진행하게 되면 미로 찾기 문제에서 거리를 저장하듯이 이전 버튼 횟수 + 1을 각각의 위치에 누적하고,
• 최종적으로 원하는 값의 위치의 버튼 횟수를 출력함으로써 문제를 해결할 수 있음
• BFS로 탐색하기 때문에 해당 위치(연산 결과)를 최초에 발견했을 때 누적 값이 최솟값임이 보장되고, 방문 여부를 검사하므로 두번 이상 방문하지 않는 것이 보장되기 때문에 정확하게 정답을 구할 수 있음

5. 전체 코드

//MARK: - 이상한 계산기

//MARK: - Framework
import Foundation

//MARK: - Variable
var N: Int = 0
let MAX: Int = 1000000
var visited: [Bool] = []

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

func solution() -> Void {
    //MARK: - Input
    var result: Int = 0
    N = Int(readLine() ?? "0") ?? 0
    visited = Array(repeating: false, count: MAX)
    
    //MARK: - Process
    result = bfs(1)
    
    //MARK: - Output
    print(result)
}
solution()

 

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