[python] 백준 14226번: 이모티콘(BFS)

# 14426 이모티콘

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

⭐ 코드

import sys
input = sys.stdin.readline
from collections import deque
S = int(input())

visited = [[-1] * (S + 1) for _ in range(S + 1)]
queue = deque()
queue.append((1,0))
visited[1][0] = 0
while queue:
    screen, clip = queue.popleft()

    if S == screen:
        print(visited[screen][clip])
        break
    
    if visited[screen][screen] == -1:
        visited[screen][screen] = visited[screen][clip] + 1
        queue.append((screen, screen))
    
    if screen + clip <= S and visited[screen + clip][clip] == -1:
        visited[screen + clip][clip] = visited[screen][clip] + 1
        queue.append((screen + clip, clip))
    
    if screen - 1 >= 0 and visited[screen - 1][clip] == -1:
        visited[screen - 1][clip] = visited[screen][clip] + 1
        queue.append((screen - 1, clip))

📝 풀이

영선이는 이미 화면에 이모티콘 1개를 입력했다. 그리고 3가지 연산을 사용해서 이모티콘 S개를 만들고자 한다. 3개의 연산은 아래와 같다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

3. 화면에 있는 이모티콘 중 하나를 삭제한다.

위와 같은 연산은 1초씩 걸리게 되며, S개의 이모티콘을 만드는데 걸리는 최솟값을 구하면 된다.

🔓 정답 코드 뜯어보기

from collections import deque
S = int(input())

visited = [[-1] * (S + 1) for _ in range(S + 1)]
queue = deque()
queue.append((1,0))
visited[1][0] = 0
# S가 2일때
# [
# [-1, -1, -1], [0, -1, -1], [-1, -1, -1]
# ]

방문을 기록할 visited 리스트를 S+1만큼 생성시켜준다.S+1을 해주는 이유는 python의 인덱스는 0부터 시작이지만, 편의상 1이라는 숫자와 인덱스 값을 일치시키기 위해 S + 1로 리스트를 생성해준다. S값에 따라 visited는 위와 같이 생성된다.

 

queue에 현재 이모티콘이 1개 있고, 0초이므로 (1,0)을 초기값으로 넣어준다. visited[1][0]에 현재 이모티콘 1개가 있고 생성하는데 걸린 시간이 0초이므로 0을 기록해준다.

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

while queue:
    screen, clip = queue.popleft()
	
    # S(목표 이모티콘 개수)와 화면의 이모티콘 개수가 맞을 때
    if S == screen:
        print(visited[screen][clip])
        break

우리가 구현해야 하는 코드는 위에 적혀있는 3가지 연산이다. 먼저 queue에 담긴 리스트를 꺼내주면서 screen과 clip 변수에 할당시켜준다. 문제에서 요구하는 정답은 S(목표 이모티콘 개수)와 화면의 이모티콘 개수가 맞을 때의 걸린 시간 이므로 첫번째 if문에 목표와 이모티콘 개수가 맞을때의 걸린 시간을 출력시켜준다.

 

1번 연산의 코드를 바꾸면 다음과 같다.

# 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
if visited[screen][screen] == -1:
    visited[screen][screen] = visited[screen][clip] + 1
    queue.append((screen, screen))

처음 설정 값이 1,0이므로 코드에 대입해보면

if visited[1][1] == -1:

visited[1][1] = visited[1][0] + 1 이 된다. visited[1][0]은 0이므로 visited[1][1]은 1이 되게 된다. [0, -1, -1]이었던 visited는 [0, 1, -1]이 되게 된다.

 

2번 연산의 코드를 바꾸면 다음과 같다.

# 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
if screen + clip <= S and visited[screen + clip][clip] == -1:
    visited[screen + clip][clip] = visited[screen][clip] + 1
    queue.append((screen + clip, clip))

screen + clip이 목표 값보다 작거나 같고, visited[screen + clip][clip]이 방문하지 않은 곳이라면 visited[screen + clip][clip]위치에 visited[screen][clip] 값에서 1을 더한 값을 저장해준다. screen이 1, clip이 0이라고 가정하면 visited[1+1] = visited[1][0] + 1 = 2 값이 저장되게 된다.

 

3번 연산의 코드를 바꾸면 다음과 같다.

# 3. 화면에 있는 이모티콘 중 하나를 삭제
if screen - 1 >= 0 and visited[screen - 1][clip] == -1:
    visited[screen - 1][clip] = visited[screen][clip] + 1
    queue.append((screen - 1, clip))

말 그대로 이모티콘 중 하나를 삭제하는 로직을 작성해준다. screen - 1이 0보다 크거나 같아야하면서 screen에서 1을 뺀 값이 방문하지 않은 곳이여야 한다. 동일하게 visited에 이모티콘 하나를 삭제 하는 연산을 수행했으므로 +1초의 시간을 더해준다. 위 구문을 모두 실행하한 후 screen과 S의 개수가 같아진다면 visited[screen][clip]값이 출력되게 된다.