[백준] 14226번: 이모티콘

문제

백준 - 14226번: 이모티콘

분석

이모티콘을 S개 보내려고 한다.
이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

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

모든 연산은 1초가 걸린다. S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 문제이다.

BFS 카테고리에서 풀지 않았다면 BFS인지 몰랐을 수도 있겠다는 생각이 들었다.
3가지 연산 중에서 실질적으로 개수에 변화가 있는 것은 삭제하거나 붙여넣는 동작이다.
따라서 다음 x 즉, nx는 x-1과 x+clip을 리스트로 묶어서 차례로 대입했다.

이 문제에서는 화면에 보여진 현재 이모티콘 개수가 같아도 클립보드의 내용이 다르면 다른 경우로 쳐야 되기 때문에 visited를 2차원 배열(현재 이모티콘 수, 클립보드 저장 수)로 만들었다.

복사하는 경우는 항상 고려해야 되기 때문에 큐에 항상 넣지만, 이미 방문한 경우엔 무시한다.

초기 화면에 보여지는 이모티콘은 1개 이므로 bfs(1)로 시작한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import deque
s = int(input())
MAX = 1000
visited = [[False]*(MAX+1) for _ in range(MAX+1)]

def in_range(x):
    return 2 <= x <= MAX

def bfs(start):
    q = deque([(start, 0, 0)])
    visited[start][0] = True
    while q:
        x, clip, t = q.popleft()
        if x == s:
            return t
        if not visited[x][x]:
            q.append((x, x, t+1))
        for nx in [x-1, x+clip]:
            if in_range(nx) and not visited[nx][clip]:
                visited[nx][clip] = True
                q.append((nx, clip, t+1))

print(bfs(1))

끝으로..

기초 BFS 문제를 많이 접했어서 기계처럼 풀었는데, 응용된 문제들을 풀어보니
쉬운 건 없구나라는 생각이 든다.