백준 14395 4연산 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/14395

14395번: 4연산

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 10^9)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

간단한 bfs 문제이다.

사전 순으로 출력해야 하기 때문에 문제에서 주어진 아스키 코드 순서로 탐색을 진행하고, bfs로 제일 먼저 나오는 답이 정답이 된다.

우리는 s를 t로 만들어야 한다. 여기서 범위를 10^9로 생각할 수 있는데, s -> t로 만드는 과정에서 s가 t보다 커지는 상황이 있을 수 있다.

따라서 Int가 아닌 Long타입을 고려해야 하며, 방문 체크는 배열에 담을 수 있는 사이즈가 아니므로 set으로 처리해 준다.

사실 어떠한 가지치기 없이도 무난하게 통과된다.

굳이 가지치기를 하자면, 세 가지 정도가 있다.

1. s==0 , t< Next continue
2. -연산 빼기, t< Next continue
3. 0>next ,  t< Next continue

다 비슷한 소린데 그냥 코드만 다를 뿐이다.

 

s==0일 때 스킵하는 이유는 s가 0이되면 더 이상 다른 수가 될 수 없고, s-s의 결과이기도 하다. 따라서 

s==0 continue나, -연산을 아에 안 하는 거나 같은 의미이다.

그리고 s가 t를 넘어가면 다시 t가 되기 위해선 /연산을 하고 1부터 탐색하는데, 1은 이미 앞에서 탐색했을 것이기 때문에 s가 t를 넘어가는 경우도 모두 무의미하다.

 

만약 코테라면 본인은 그냥 -연산만 제거한 코드를 제출할 것 같다.

 

String에 대한 얘기를 하자면, 처음에 큐에 String 말고 StringBuilder를 넣었었다.

만약 dfs라면

sb.append(next)

dfs()

sb.deleteCharAt(lastIdx)

로, StringBuilder의 이점을 살릴 수 있는데,

 

bfs 같은 경우

sb.append(next)

q.add(sb)

sb.deleteCharAt(lastIdx)

이런 식으로 하게 되면 모두 같은 sb를 참조하게 되어 string값이 원하는 대로 나오지 않는다.

따라서 큐에 문자열을 삽입할 때마다 어차피 DeepCopy로 넣어주어야 하니 StringBuilder의 이점을 살릴 수 없어 그냥 String으로 해도 되는 것이다.

  

코드

import java.util.*

val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

val map = mutableMapOf(
    Pair(0,'*'),
    Pair(1,'+'),
    Pair(2,'-'),
    Pair(3,'/')
)
val visited = mutableSetOf<Long>()

fun cal(num: Long, ch: Char) : Long{
    return when(ch){
        '*' -> num*num
        '+' -> num+num
        '-' -> num-num
        '/' -> num/num
        else -> 0
    }
}

fun bfs(s: Int, t: Int) : String {
    val q : Queue<Pair<Long,String>> = LinkedList()
    q.add(Pair(s.toLong(), ""))

    while(q.isNotEmpty()){
        val cur = q.poll()

        for(i in 0 until 4){
            if(cur.first==0L) continue
            val nextNum = cal(cur.first,map[i]!!)
            //종료
            if(nextNum == t.toLong()){
                return cur.second+map[i]
            }
            if(nextNum !in 1 .. t) continue
            if(visited.contains(nextNum)) continue

            q.add(Pair(nextNum, cur.second + map[i]))
            visited.add(nextNum)
        }
    }
    return "-1"
}

fun main() = with(System.out.bufferedWriter()){

    //input
    val (s,t) = getIntList().apply{
        if(this[0] == this[1]){
            write("0")
            close()
            return
        }
    }
    //solve, output
    write("${bfs(s,t)}")

    close()
}