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

문제

---

생각하기

---

• 문자열을 K번 바꾸면서 최대값을 찾는 문제이다.

• BFS를 통해서 문자열을 바꾸고, 최적화를 위해 메모이제이션을 사용하면 풀 수 있다.

동작

결과

코드

---

Kotlin

BFS

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

// input
private lateinit var br: BufferedReader

// variables
private const val MAX = 1_000_001
private var N = 0
private var K = 0
private var ans = 0
private lateinit var memo: Array<BooleanArray>

private data class Pair(var num: Int, var k: Int)

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    BFS()
    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun BFS(): Int {
    val que = LinkedList<Pair>()
    que.offer(Pair(N, 0))

    while (que.isNotEmpty()) {
        val nowNode = que.poll()

        if (nowNode.k == K) {
            ans = ans.coerceAtLeast(nowNode.num)
            continue
        }

        if (memo[nowNode.k][nowNode.num]) continue
        memo[nowNode.k][nowNode.num] = true

        val strNum = nowNode.num.toString()
        val len = strNum.length
        for (i in 0 until len - 1) {
            for (j in i + 1 until len) {
                if (i == 0 && strNum[j] == '0') continue

                val swapped = swap(strNum, i, j)
                val swappedNum = swapped.toInt()

                que.offer(Pair(swappedNum, nowNode.k + 1))
            }
        }
    }

    return ans
} // End of BFS()

private fun swap(str: String, i: Int, j: Int): String {
    val arr = str.toCharArray()
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    return String(arr)
} // End of swap

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        K = nextToken().toInt()
    }

    ans = -1
    memo = Array(K + 1) { BooleanArray(MAX) }
} // End of input()

DFS

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var K = 0
private var ans = 0
private lateinit var memo: Array<BooleanArray>

private data class Pair(var num: Int, var k: Int)

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    BFS()
    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun BFS(): Int {
    val que = LinkedList<Pair>()
    que.offer(Pair(N, 0))

    while (que.isNotEmpty()) {
        val nowNode = que.poll()

        if (nowNode.k == K) {
            ans = ans.coerceAtLeast(nowNode.num)
            continue
        }

        if (memo[nowNode.num][nowNode.k]) continue
        memo[nowNode.num][nowNode.k] = true

        val strNum = nowNode.num.toString()
        val len = strNum.length
        for (i in 0 until len - 1) {
            for (j in i + 1 until len) {
                if (i == 0 && strNum[j] == '0') continue

                val swapped = swap(strNum, i, j)
                val swappedNum = swapped.toInt()

                que.offer(Pair(swappedNum, nowNode.k + 1))
            }
        }
    }

    return ans
} // End of BFS()

private fun swap(str: String, i: Int, j: Int): String {
    val arr = str.toCharArray()
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    return String(arr)
} // End of swap

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        K = nextToken().toInt()
    }

    ans = -1
    memo = Array(1_000_001) { BooleanArray(K + 1) }
} // End of input()