[백준][코틀린][14395] 4연산

https://www.acmicpc.net/problem/14395

14395번: 4연산

문제 풀이

1. 문제를 4가지 연산에 대해서 BFS 를 수행한다. 이때 연산자 순서(*, +, -, /) 에 맞게 탐색을 한다.

2. 이미 연산된 결과를 확인하기 위해서 Boolean 배열을 사용할 경우 10억개의 크기를 가지므로 에러가 발생하기 때문에 중복 조건을 확인할 수 있는 Set 자료구조를 사용한다.

3. 나눗셈 연산 시 탐색할 숫자가 0일 경우에는 다음 탐색을 수행한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (s, t) = br.readLine().split(" ").map { it.toInt() }

    if (s == t) {
        println(0)
    } else {
        println(bfs(s, t))
    }
}

private fun bfs(s: Int, t: Int): String {
    val queue = LinkedList<Pair<Long, String>>()
    queue.add(Pair(s.toLong(), ""))
    val check = mutableListOf<Long>()

    while (queue.isNotEmpty()) {
        val current = queue.pop()

        if (current.first == t.toLong()) return current.second

        for (i in 0..3) {
            if (i == 3 && current.first == 0L) continue

            val nextNumber = when (i) {
                0 -> current.first * current.first
                1 -> current.first + current.first
                2 -> 0
                else -> 1
            }

            if (check.contains(nextNumber)) continue

            check.add(nextNumber)
            queue.add(Pair(nextNumber, "${current.second}${getOp(i)}"))
        }
    }


    return "-1"
}

private fun getOp(index: Int): String {
    return when (index) {
        0 -> "*"
        1 -> "+"
        2 -> "-"
        else -> "/"
    }
}