[백준 14226] 이모티콘(Python)

1. 요약

화면에 이모티콘이 1개가 있는데, 다음 연산들을 이용하여 이모티콘을 S개 만든다.

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

각 연산은 1초가 걸리며, 우리가 해야할 일을 최소 시간으로 이모티콘을 S개 만드는 것이다.

(단, 클립보드에 이모티콘을 복사하면, 이전에 존재하는 내용은 사라진다. 또한 클립보드가 비어있는 상태에서 화면으로 붙여넣기를 할 수 없다.)

2. 아이디어

BFS로 해결한다.

화면에 있는 이모티콘의 수, 클립보드에 있는 이모티콘의 수에 접근 했는 지를 알려주는 2차원 방문 배열을 이용한다.(i.e. visited[scnt][ccnt])

주의

만약 화면에 있는 이모티콘의 수에 접근한 것만 고려하면, 클립보드에 있는 이모티콘을 화면에 복사하는 것을 1번만 수행하는데 이것은 문제가 될 수 있다.

예를 들어 S가 9라고 하면, 연산의 순서가 122122로 총 6번이 되어야하는데, 화면 이모티콘의 수에 접근하는 것만 고려하면, 방문한 곳을 다시 방문하게 되는 것 이므로 3번째 연산인 2가 수행되지 않는다. 따라서 방문처리를 할 때, 클립보드도 고려해야한다.

3. 코드

import sys
from collections import deque

s = int(sys.stdin.readline().rstrip())

def isin(y,x):
    if y < 1500 and x < 1500: return True
    return False

def solve():
    visited = [[False for _ in range(1500)] for _ in range(1500)]
    q = deque()
    # 시간, 화면에 출력되는 이모티콘, 클립보드에 저장된 이모티콘
    q.append([0, 1, 0])
    visited[1][0] = True

    while q:
        sec, scnt, ccnt = q.popleft()
     
        if scnt == s:
            print(sec)
            break

        # 화면에 있는 이모티콘을 클립보드에 복사
        next_ccnt = scnt
        if not visited[scnt][next_ccnt]:
            visited[scnt][next_ccnt] = True
            q.append([sec+1, scnt, next_ccnt])

        # 클립보드에 있는 이모티콘을 화면에 복사
        if ccnt > 0:
            next_scnt = scnt + ccnt
            if isin(next_scnt, ccnt) and not visited[next_scnt][ccnt]:
                visited[next_scnt][ccnt] = True
                q.append([sec+1, next_scnt, ccnt])
        
        # 화면에 있는 이모티콘 제거
        if scnt > 1:
            next_scnt = scnt - 1
            if isin(next_scnt, ccnt) and not visited[next_scnt][ccnt]:
                visited[next_scnt][ccnt] = True
                q.append([sec+1, next_scnt, ccnt])
            
solve()