[알고리즘/Swift] 14226 이모티콘

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크:
  • 14226 이모티콘
• 제출 언어: Swift
• 알고리즘 분류:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색

---

풀이

(1(초기 화면 개수), 0(초기 클립보드 개수), 0(연산 횟수)) 튜플을 큐에 넣어준 후, 하나씩 pop 해주며 해당 조건에 맞으면, 복사, 붙여넣기, 하나 삭제하기 연산을 수행한다. pop 했을 경우 원하고자 하는 이모티콘의 개수 S개가 되면 반복문을 종료하고 출력한다

• visited 배열에 display의 방문 여부를 따지면 클립보드내의 개수와 상관없이 한 번만 고려하게 되므로 visited[display][clip] 배열에 방문한 곳을 기록한다
• visited 배열은 S의 값이 최대 1000 이므로 1000 x 1000 배열로 생성해주었다
• 가장 처음 상태에서 복사를 해야하므로 복사하기 조건을 고려할 때 복사 후의 화면의 이모티콘의 개수가 1~=1000 범위안에 들도록 하였다
• 하나 삭제하기 연산은 삭제 후의 화면의 이모티콘의 개수가 2~=1000 범위안에 들도록 하였다 (S의 범위)
• 붙여넣기 연산은 클립보드에 이모티콘이 있고, 붙여넣기한 후의 화면의 이모티콘의 개수가 1000개 이하가 되도록 하였다
• 각각 연산시에 visited[display+clip][clip] = true 를 해주고 큐에 연산한 튜플을 넣어주었다
• 방문을 true로 할 때, pop한 후에 하는 것보다 push할 때 시간복잡도가 더 빨랐다

// 시간 초과
let (display, clip, time) = queue.popFirst()
visited[display][clip] = true

코드

import Foundation
class Queue<T> {
    var inbox: [T]
    var outbox: [T] = []
    
    var count: Int {
        return inbox.count + outbox.count
    }
    
    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }
    
    init(_ queue: [T]) {
        inbox = queue
    }
    
    func pushLast(_ element: T) {
        inbox.append(element)
    }
    
    func pushFirst(_ element: T) {
        outbox.append(element)
    }
    
    func popLast() -> T {
        if inbox.isEmpty {
            inbox = outbox.reversed()
            outbox.removeAll()
        }
        return inbox.popLast()!
    }
    
    func popFirst() -> T {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.popLast()!
    }
}

let S = Int(readLine()!)!
var queue = Queue([(1, 0, 0)])
var visited = Array(repeating: Array(repeating: false, count: 2000), count: 2000)

while !queue.isEmpty {
    let (display, clip, time) = queue.popFirst()
    if display == S {
        print(time)
        break
    }
    // 복사하기
    if (1...1000) ~= display {
        if !visited[display][display] {
            visited[display][display] = true
            queue.pushLast((display, display, time+1))
        }
    }
    // 삭제하기
    if (2...1000) ~= display-1 {
        if !visited[display-1][clip] {
            visited[display-1][clip] = true
            queue.pushLast((display-1, clip, time+1))
        }
    }
    // 붙여넣기
    // 클립보드가 비어있지 않고, 붙여넣는 값과 화면의 값의 합이 1000을 넘지 않는 경우
    if clip > 0 && display+clip <= 1000 {
        if !visited[display+clip][clip] {
            visited[display+clip][clip] = true
            queue.pushLast((display+clip, clip, time+1))
        }
    }
}