[백준] #14226. 이모티콘 (파이썬/Python)

📖 문제

[백준] #14226. 이모티콘 (파이썬/Python)

• 난이도: 골드4
• 유형: BFS

문제 요약

• 현재 화면에는 😃 이모티콘 1개가 있다.
• 목표: S개의 이모티콘을 화면에 만들기 위한 최소 시간을 구해야 한다.
• 사용할 수 있는 연산은 다음 3가지이다. (모두 1초 소요)

연산 설명

1. 복사	화면에 있는 이모티콘 전부를 클립보드에 복사
2. 붙여넣기	클립보드 내용을 화면에 붙여넣기
3. 삭제	화면에서 이모티콘 하나 삭제

※ 클립보드가 비어있으면 붙여넣기를 할 수 없다.

※ 클립보드, 화면 모두 "일부 선택"은 불가능하며 전량 복사/붙여넣기/삭제만 가능하다.

---

🔍 문제 접근

💡 문제 분석

• "최소 시간" → BFS로 탐색해야 한다.
• 일반적인 BFS와 달리, 상태를 구성하는 요소가 2가지이다.
  • 현재 화면 이모티콘 수
  • 현재 클립보드 이모티콘 수

 

🧠 풀이 아이디어

• BFS 상태 트리에서 하나의 노드는 `(화면 개수, 클립보드 개수)` 형태이다.
• BFS는 `(1, 0)`에서 시작한다. (초기 상태: 화면에 이모티콘 1개, 클립보드는 비어 있음)
• 방문 처리는 `visited[screen][clipboard]` 이차원 배열로 관리한다.
• S개의 이모티콘을 만들었을 때, 걸린 시간을 바로 출력하면 된다.

 

---

🔍 문제 풀이

♻️ 코드 플로우

• BFS 큐에는 `(화면, 클립보드)` 상태를 저장한다.
• 각 상태에서 다음 세 가지 연산을 수행할 수 있다:
  1. 복사: `(screen, screen)`
  2. 붙여넣기: `(screen + clipboard, clipboard)` — 단, clipboard가 0이 아니어야 함
  3. 삭제: `(screen - 1, clipboard)`
• 연산 수행 후 범위 확인 및 `visited` 체크를 통해 중복 방문을 방지한다.
• 목표 개수인 `S`에 도달하면 해당 시간을 출력하고 종료한다.

 

🚩 제출한 소스 코드

import sys
from collections import deque
input = sys.stdin.readline

# 1. 입력 및 초기화
S = int(input())
MAX = 1001

# visited[screen][clipboard] = 해당 상태까지 걸린 시간
visited = [[-1] * MAX for _ in range(MAX)]
visited[1][0] = 0

queue = deque([(1, 0)]) # 화면 임티 개수, 클립보드 임티 개수

# 2. BFS 탐색
while queue:
    screen, clip = queue.popleft()

		# 3. 목표 달성 시 종료
    if screen == S:
        print(visited[screen][clip])
        break

    for i in range(3):
        if i == 0: # 복사 (화면 → 클립보드)
            new_screen, new_clipboard = screen, screen
        elif i == 1: # 붙여넣기 (클립보드 → 화면)
            new_screen, new_clipboard = screen + clip, clip
        else: # 삭제 (화면 - 1)
            new_screen, new_clipboard = screen - 1, clip

        if new_screen >= MAX or new_screen < 0 \
                or new_clipboard >= MAX or new_clipboard < 0 \
                or visited[new_screen][new_clipboard] != -1:
            continue

        visited[new_screen][new_clipboard] = visited[screen][clip] + 1
        queue.append((new_screen, new_clipboard))

 

🚩 다른 분의 풀이

[백준] boj-14226 이모티콘 파이썬

from collections import deque
n = int(input())
dist = [[-1]* (n+1) for _ in range(n+1)]
q = deque()
q.append((1,0))  # 화면 이모티콘 개수, 클립보드 이모티콘 개수
dist[1][0] = 0
while q:
    s,c = q.popleft()
    if dist[s][s] == -1: # 방문하지 않았으면
        dist[s][s] = dist[s][c] + 1
        q.append((s,s))
    if s+c <= n and dist[s+c][c] == -1:
        dist[s+c][c] = dist[s][c] + 1
        q.append((s+c, c))
    if s-1 >= 0 and dist[s-1][c] == -1:
        dist[s-1][c] = dist[s][c] + 1
        q.append((s-1, c))
answer = -1
for i in range(n+1):
    if dist[n][i] != -1:
        if answer == -1 or answer > dist[n][i]:
            answer = dist[n][i]
print(answer)

 

백준 14226번 이모티콘 | python | bfs

import sys
from collections import deque
from pprint import pprint

input = sys.stdin.readline

s = int(input().strip())
visited = [[0] * 1001 for _ in range(1001)]  # 카운트 세는 리스트


def bfs():
    q = deque()
    ans = 0
    q.append((1, 0))  # (화면에 존재하는 이모티콘 개수,현재 클립보드에 저장된 이모티콘 개수)
    while q:
        x_screen, x_clip = q.popleft()
        if x_screen == s:
            ans = visited[x_screen][x_clip]
            break

        arr = [
            (x_screen, x_screen),
            (x_screen + x_clip, x_clip),
            (x_screen - 1, x_clip),
        ]

        for screen, clip in arr:
            if 0 <= screen < 1001 and 0 <= clip < 1001 and not visited[screen][clip]:
                # 첫 번째 경우
                q.append((screen, clip))  # 현재 화면에 존재하는 이모티콘 개수 만큼 클립보드에 저장
                visited[screen][clip] = visited[x_screen][x_clip] + 1

    return ans


print(bfs())

 

---

💡회고

• 지난 숨바꼭질2 문제와 비슷하게 최소 시간만 저장해야 할 것이 아닌 클립보드의 이모티콘 개수도 함께 저장해야 한다는 점에서 큰 아이디어가 비슷하다.
• 범위를 MAX값을 1001로 지정해야 했는데 1000으로 지정한 점 등 잘못 지정한 게 많았기에 시간 내에 풀지 못해 아쉽다.