[백준] 14226. 이모티콘 (Kotlin)

문제

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

풀이

0. 문제 해석

 

1초에 걸쳐

 

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

 

3가지 연산 중 하나를 할 수 있다.

일단 시간의 최솟값을 구하는 문제이므로 3가지 연산에 대한 BFS를 사용한다.

 

여기서 방문처리를 어떻게 해야하는지가 문제인데,

 

예를 들어 4의 경우

 

1 - 2 - 3 - 4

복 - 붙 - 붙 - 붙

 

의 형태로 만들 수 있고

 

1 - 2 - 2 - 4

복 - 붙 - 복 - 붙

 

의 형태로도 만들 수 있다.

위 둘의 경우를 따로 체크해줘야 한다.

같이 체크했을 경우 후자의 경우는 이미 방문한 4를 방문하므로 탐색이 진행되지 않을 것인데,

 

이제 다음 탐색을 살펴보면

전자의 경우

 

1 - 2 - 3 - 4 - 5 - 6

복 - 붙 - 붙 - 붙 - 붙 - 붙

이런식으로 갈 수 있다. (수를 늘리는 경우만 봤을 때)

 

하지만 후자의 경우

 

1 - 2 - 2 - 4 - 6

복 - 붙 - 복 - 붙 - 붙

이런식으로 6을 만드는데 5의 시간이 걸리는 것을 알 수 있다.

 

따라서 모든 경우를 고려해주려면

2차원 배열로 현재 길이와, 그 길이를 방문했을 때 클립보드에 저장되어 있는 길이를 같이 포함하여 방문처리 해야한다.

 

또한 다음 탐색을 진행할 queue에 넣을 값도 현재 길이와, 그 길이를 방문했을 때 클립보드에 저장되어 있는 길이 를 넣어주어 탐색해야 한다.

 

 

1. 전체 코드

// [백준] 14226. 이모티콘 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

var s = 0
const val MAX_SIZE = 1000 + 1
lateinit var visit : Array<Array<Boolean>>

// 길이, 클립보드
data class Emoji(var len: Int, var clip: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    s = readLine().toInt()
    visit = Array(MAX_SIZE) { Array(MAX_SIZE) { false } }
    bfs()
}

fun bfs(){
    val q : Queue<Emoji> = LinkedList()
    q.offer(Emoji(1, 0))
    visit[1][0] = true

    var time = 0
    while(q.isNotEmpty()){
        val size = q.size

        // 레벨 체크
        for(i in 0 until size){
            val cur = q.poll()

            if(cur.len == s){
                println(time)
                return
            }

            // 정답의 범위
            if(cur.len in 1 .. 1000){

                // 클립보드에 현재 이모티콘 복사
                if(!visit[cur.len][cur.len]){
                    visit[cur.len][cur.len] = true;
                    q.offer(Emoji(cur.len, cur.len))
                }

                // 현재 복사되어 있는 이모티콘 붙여넣기
                if(cur.len + cur.clip < MAX_SIZE){
                    if(!visit[cur.len + cur.clip][cur.clip]){
                        visit[cur.len + cur.clip][cur.clip] = true
                        q.offer(Emoji(cur.len + cur.clip, cur.clip))
                    }
                }

                // 이모티콘 1개 삭제
                if(!visit[cur.len - 1][cur.clip]){
                    visit[cur.len - 1][cur.clip] = true
                    q.offer(Emoji(cur.len - 1, cur.clip))
                }
            }
        }
        time++
    }
}