[알고리즘] DSLR (백준 9019번)

9019번: DSLR

 특정 목적지점까지 가는데 필요한 최소해를 구하는 BFS 완전탐색 문제다.

 

Solution

전체 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.StringBuilder
import java.util.*

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


fun solution() {

    var T = br.readLine().toInt()

    for(t in 0 until T)
    {
        var strtok = StringTokenizer(br.readLine())
        var A = strtok.nextToken().toInt()
        var B = strtok.nextToken().toInt()

        var visited = BooleanArray(10000)

        var queue : Queue<Register> = LinkedList()
        queue.offer(Register(A, ""))
        visited[A] = true

        while(!queue.isEmpty())
        {
            var now = queue.poll()

            //목적지 도착
            if(now.register_value == B)
            {
                bw.write(now.orders)
                bw.newLine()
                break
            }

            //1. D
            var next = (now.register_value * 2) % 10000

            if(!visited[next])
            {
                visited[next] = true
                queue.offer(Register(next, now.orders + "D"))
            }

            //2. S
            next = now.register_value - 1
            if(next == -1)
                next = 9999

            if(!visited[next])
            {
                visited[next] = true
                queue.offer(Register(next, now.orders + "S"))
            }

            //3. L
            next = rotationNumbers(now.register_value, 'L')

            if(!visited[next])
            {
                visited[next] = true
                queue.offer(Register(next, now.orders + "L"))
            }

            //4. R
            next = rotationNumbers(now.register_value, 'R')

            if(!visited[next])
            {
                visited[next] = true
                queue.offer(Register(next, now.orders + "R"))
            }
        }

    }
}

fun rotationNumbers(origin_num : Int, dir : Char) : Int
{
    var origin_num = origin_num

    if(dir == 'L')
    {
        var d1 = origin_num / 1000
        origin_num -= d1 * 1000
        origin_num *= 10
        origin_num += d1
    }
    else
    {
        var d4 = origin_num % 10
        origin_num /= 10
        origin_num += d4 * 1000
    }
    return origin_num
}


data class Register(var register_value:Int, var orders: String)

fun main() {
    solution()
    br.close()
    bw.close()
}

• 노드 : 레지스터의 십진수
• 간선 : D, S, L, R 노드마다 총 4가지

 눈 여겨볼 부분은 L, R 일 경우에 정수를 왼쪽, 오른쪽으로 회전시키는 것이다.

1. L 일 경우
   1. 십진수 / 1000을 하여서 1000의 자리 숫자인 d1을 구한다 EX) 1234 / 1000 = 1
   2. 십진수에서 d1 * 1000을 빼고 10을 곱한다. EX) (1234 - 1000) * 10 = 2340
   3. 십진수에 d1을 더한다. EX) 2340 + 1 = 2341
2. R 일 경우
   1. 십진수 % 10을 하여서 1의 자리 숫자인 d4를 구한다 EX) 1234 % 10 = 4
   2. 십진수 / 10을 한다. EX) 1234 / 10 = 123
   3. 십진수에 d4에 1000을 곱한 수를 더한다. EX) 123 + (4 * 1000) = 4123