백준 이모티콘 - 14226

코드

import java.util.*


fun main() {
    val target = readLine()!!.toInt()

    val set = HashSet<String>()

    val queue = LinkedList<Node>()
    set.add("1 0")
    queue.offer(Node(1,0,0))


    while (!queue.isEmpty()) {
        val node = queue.poll()
        if (node.total == target) {
            println(node.time)
            break
        }

        // 1. 현재 클립 보드 붙이기
        if (!set.contains("${node.total+node.clipboard} ${node.clipboard}")) {
            set.add("${node.total+node.clipboard} ${node.clipboard}")
            queue.offer(Node(node.total+node.clipboard, node.clipboard,node.time+1))
        }


        // 2. 현재 이모티콘 복사
        if (!set.contains("${node.total} ${node.total}")) {
            set.add("${node.total} ${node.total}")
            queue.offer(Node(node.total,node.total,node.time+1))
        }


        // 3. 화면 이모티콘 삭제
        if (node.total > 0 && !set.contains("${node.total-1} ${node.clipboard}")) {
            set.add("${node.total-1} ${node.clipboard}")
            queue.offer(Node(node.total-1,node.clipboard,node.time+1))
        }

    }
}

private class Node(val total:Int,val clipboard:Int,val time:Int)

해설

bfs를 활용하여 문제를 해결하였습니다.

주요 구성 요소

• Set 선언 : 해당 set의 경우 방문한 적이 있는지 확인하기 위해 선언해주었습니다.
• Queue 선언 : queue의 경우 Node를 넣을 수 있게 선언하였습니다. 이를 통해 bfs를 구현 할 것입니다.
• Node class 선언 : total의 경우 현재 이모티콘의 개수를 clipboard의 경우 클립보드에 있는 이모티콘의 개수를 의미합니다.

로직

1. 시작 Node인 total:1, clipboard:0 인 상태의 node를 생성하여 queue에 넣어줍니다.
2. queue가 비어있을때까지 로직을 수행합니다.
3. 목표 숫자에 도달한 경우 종료 아니라면 다음 로직 수행
4. 문제조건에 맞게 각 node를 생성하여 넣어줍니다. 이 때 넣어주기전에 Set을 활용하여 이미 방문한 적이 있는 경우에는 넣어주지 않고 그대로 진행합니다.
   • set의 경우 숫자만을 보고 판단하는 것이 아니고 total과 clipboard 2개를 이용하여야 하기에 Setdp "toatl개수 clipbaord개수" 형태로 넣어 판단할 수 있도록 하였습니다.예: "1 0"

출처 : [Gold IV] 이모티콘 - 14226