백준 14395 번
https://www.acmicpc.net/problem/14395

문제

---

생각하기

---

• BFS 문제이다.

  • 풀다보니까 DFS로도 풀 수 있을 것 같다는 생각이 드는데 일단 BFS여서 나는 이걸로 풀었다

• 생각보다 그리 어려운 문제는 아닌 것 같은데, 어느 깊이에서 끊어야 되는지를 못찾아서 한참 헤맸다

동작

    val set = HashSet<Long>()
    que.offer(Number(S, 0, ""))

먼저 BFS로 풀기때문에 que에 값을 넣고, HashSet이 필요한데 필요한 이유는 중복되는 값을 넣지 않기 위해서 사용된다.

굳이 HashSet을 사용하지 않고 isVisited같은 boolean 배열을 사용하거나 ArrayList를 사용해서 중복된 값이 있는지를 체크하는 것도 하나의 방법이 될 수 있을 것 같다.

        for (i in 0 until 4) {
            var nowNum = poll.num
            var nowDepth = poll.depth
            var nowOper = poll.oper

            if (i == 0) {
                nowNum *= nowNum
                nowOper += "*"
            } else if (i == 1) {
                nowNum += nowNum
                nowOper += "+"
            } else if (i == 2) {
                nowNum -= nowNum
                nowOper += "-"
            } else if (i == 3 && nowNum != 0L) {
                nowNum /= nowNum
                nowOper += "/"
            }

            if (nowNum == T) {
                ans = nowOper
                return nowDepth
            } else if (!set.contains(nowNum)) {
                set.add(nowNum)
                que.offer(Number(nowNum, nowDepth + 1, nowOper))
            }
        }

문제에서 4가지의 아스키 연산 순서가 * , + , - , / 순서라고 나와있으므로
해당 순서에 맞게 반복을 하도록 해서 연산을 해주면 된다.

중복된 값이 아닐 경우에는 que에 계속 넣어서 너비 탐색을 하면 되고 처음으로 만나게되는 T의 값이 정답이 되게된다.

코드

---

Kotlin

import java.util.*
import java.io.*

private var S = 0L
private var T = 0L

private var result = Int.MAX_VALUE
private var ans = ""

private data class Number(var num: Long = 0, var depth: Int = 0, var oper: String = "")

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val st = StringTokenizer(br.readLine())
    S = st.nextToken().toLong()
    T = st.nextToken().toLong()

    if (S == T) {
        println(0)
        return
    }


    if(BFS() == -1) {
        println(-1)
    } else {
        println(ans)
    }

} // End of main

private fun BFS(): Int {
    val que: Queue<Number> = LinkedList()
    val set = HashSet<Long>()
    que.offer(Number(S, 0, ""))

    while (!que.isEmpty()) {
        val poll = que.poll()

        for (i in 0 until 4) {
            var nowNum = poll.num
            var nowDepth = poll.depth
            var nowOper = poll.oper

            if (i == 0) {
                nowNum *= nowNum
                nowOper += "*"
            } else if (i == 1) {
                nowNum += nowNum
                nowOper += "+"
            } else if (i == 2) {
                nowNum -= nowNum
                nowOper += "-"
            } else if (i == 3 && nowNum != 0L) {
                nowNum /= nowNum
                nowOper += "/"
            }

            if (nowNum == T) {
                ans = nowOper
                return nowDepth
            } else if (!set.contains(nowNum)) {
                set.add(nowNum)
                que.offer(Number(nowNum, nowDepth + 1, nowOper))
            }
        }
    }

    return -1
} // End of BFS