BOJ 14226 - 이모티콘

문제

백준 온라인 저지 - 14226번

풀이 과정

수행할 수 있는 연산의 종류가 3가지 일 때, 이모티콘 1개에서 N 개로 만들기 위한 최소 연산의 횟수를 구하는 문제입니다.

현재 상태를 나타내는 변수는 화면에 존재하는 이모티콘의 수 와 클립보드에 있는 이모티콘의 수 이므로
이 두 변수를 상태공산의 매개변수로 정합니다.
주의할 점은 클립보드에 저장된 이모티콘을 화면에 붙여넣기 한다고 클립보드에서 삭제되지는 않는다는 것입니다.

코드

from collections import deque

S = int(input())


def bfs():
    q = deque()
    visit = [[0] * (2 * S + 1) for _ in range(2 * S + 1)]

    q.append([1, 0, 0])
    visit[1][0] = 1

    while q:
        here, clipboard, time = q.popleft()

        if here == S:
            return time

        # 화면에 있는 이모티콘 중 하나 삭제
        if here > 0 and not visit[here - 1][clipboard]:
            visit[here - 1][clipboard] = 1
            q.append([here - 1, clipboard, time + 1])

        # 클립보드에 있는 모든 이모티콘 화면에 붙여넣기
        if clipboard and here + clipboard <= 2 * S and not visit[here + clipboard][clipboard]:
            visit[here + clipboard][clipboard] = 1
            q.append([here + clipboard, clipboard, time + 1])

        # 화면에 있는 이모티콘 복사해서 클립보드에 저장
        if here > 0 and here != clipboard and not visit[here][here]:
            visit[here][here] = 1
            q.append([here, here, time + 1])


def solution():
    answer = bfs()

    return answer


print(solution())