프로그래머스 - 숫자 변환하기

언어 : Kotlin

 

x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요.

 

라는 문제다 최소 연산 횟수니까 bfs 를 선택하는게 맞았지만

처음에는 dfs 로 풀면 풀릴거 같은데? 라고 생각하고 풀었다.결과는 시간초과 나는 케이스가 있어서 실패.아래는 bfs 풀이다.내용 자체는 단순해서 bfs에 대해서 이해하고 있다면 풀이가 어렵진 않다.

import java.util.LinkedList
import java.util.Queue

lateinit var answer: ArrayList<Int>
lateinit var queue: Queue<Pair<Int, Int>>
lateinit var visited: HashMap<Int, Boolean>

class Solution {
    fun solution(x: Int, y: Int, n: Int): Int {
        answer = arrayListOf()
        queue = LinkedList()
        visited = hashMapOf()

        bfs(x, y, n, 0)

        return if (answer.isEmpty()) -1 else answer.first()
    }

    fun bfs(x: Int, y: Int, n: Int, depth: Int) {
        queue.add(Pair(x, depth))

        while (queue.isNotEmpty()) {
            val node = queue.poll()

            if (node.first > y) continue
            if (node.first == y) {
                answer.add(node.second)
                break
            }

            if (visited[node.first + n] != true) {
                queue.add(Pair(node.first + n, node.second + 1))
                visited[node.first + n] = true
            }
            if (visited[node.first * 2] != true) {
                queue.add(Pair(node.first * 2, node.second + 1))
                visited[node.first * 2] = true
            }
            if (visited[node.first * 3] != true) {
                queue.add(Pair(node.first * 3, node.second + 1))
                visited[node.first * 3] = true
            }
        }
    }
}