14226. 이모티콘 [BAEKJOON / Python]

문제

 

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

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

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

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

input = 2
output = 2

input = 18
output = 8

 

 

전체 코드

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 screen == S:
        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:           # 화면과 클립보드의 이모티콘 개수가 S를 넘지 않을 경우로 범위를 지정해준다.
        visited[screen + clip][clip] = visited[screen][clip] + 1
        queue.append((screen + clip, clip))
        
    # 화면 이모티콘 1개 삭제
    if screen - 1 >= 0 and visited[screen - 1][clip] == -1:                 # 화면에서 이모티콘을 하나 삭제할 때 -가 될 경우를 방지하여 범위를 지정해준다.
        visited[screen - 1][clip] = visited[screen][clip] + 1
        queue.append((screen - 1, clip))

 

 

문제 풀이 포인트

• BFS
• 2차원 방문 리스트
  • 방문 리스트로 화면 & 클립보드의 이모티콘 개수 파악
  • 해당 좌표값은 이모티콘을 만드는 시간

 

로직

1. 2차원 방문 리스트를 만들어 준다.
2. deque을 이용해 시작 좌표값을 넣어준다. 이미 화면에 1개의 이모티콘이 있으므로 (1, 0)을 할당한다. 또한, 시작 좌표의 방문 리스트 값을 0으로 할당한다. (0초)
3. 문제에서의 각 조건들을 각각의 if문으로 작성한다.
4. 화면에 목표한 이모티콘 개수로 채워졌다면 해당 좌표값(걸린 시간)을 출력하고 while문을 멈춘다.

 

 

코드 디테일

2차원 방문리스트 생성 및 시작 좌표, 좌표값 할당

 

S = int(input())
visited = [[-1] * (S + 1) for _ in range(S + 1)]
queue = deque()
queue.append((1, 0))
visited[1][0] = 0

visited라는 방문 리스트를 -1값으로 행렬 개수 S + 1만큼 생성한다.

 

❓ -1의 값으로 만드는 이유

→ 0의 값으로 이루어진 2차원 리스트를 재차 방문할 시 해당 좌표 값이 2 혹은 그 이상이 되어버린다. 

또한, 시작값(시작 시간)이 0초이므로 이와 혼선을 주지 않고, 불필요한 연산을 줄이기 위해 방문 리스트 값을 애초에 -1로 설정하는 것이다.

 

❓ S가 아닌 S + 1로 방문 리스트를 생성하는 이유

→ 방문 리스트의 인덱스가 곧 화면과 클립보드의 이모티콘 개수이기 때문이다.

리스트의 인덱스는 0부터 시작하므로 S(목표 이모티콘 개수)에 맞춰 +1을 해준다.

 

문제에서 이미 화면에 1개의 이모티콘이 있으므로 queue에 (1, 0)의 값을 할당한다. 

또한 시작되는 좌표이므로 방문리스트의 [1][0]의 값은 0으로 설정한다.

 

즉, 방문 리스트의 인덱스값은 화면과 클립보드에 있는 이모티콘의 개수이다.

해당 인덱스의 값은 이모티콘이 S개까지 생성될 때 걸리는 시간이다.

 

 

이제 while문 안에 있는 if문들을 살펴보자.

 

이모티콘이 목표 개수(S)에 도달했을 때 => 정답 출력

while queue:
    screen, clip = queue.popleft()
    
    if screen == S:
            print(visited[screen][clip])
            break

while문이 시작될 때 queue에 할당될 조건에 맞는 좌표값(화면 및 클립보드 이모티콘 개수)을 각 screen, clip 변수에 할당한다.

 

첫번째 if문은 정답을 출력하는 구문이다.

즉, 방문 리스트에서 screen에 해당하는 인덱스가 S갑과 같은 인덱스에 도달하게 된다면 이모티콘이 목표 개수만큼 생성된 것이므로 해당 좌표값을 출력한다.

 

화면의 이모티콘 개수를 클립보드에 저장

    if visited[screen][screen] == -1:
        visited[screen][screen] = visited[screen][clip] + 1
        queue.append((screen, screen))

화면의 이모티콘 개수를 클립보드에 저장하기 위해서 

visited[screen][clip] → visited[screen][screen] 처럼 클립보드를 할당하는 인덱스가 아닌 screen 인덱스를 적어준다. 

하나의 행위를 할 때는 1초의 시간이 걸리기 때문에 해당 좌표값에 1을 더해준다.

 

현재 visited[screen][clip]의 값은 위 코드에서 0을 할당해주었기 때문에 (시작값) 1의 값이 visited[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))

클립보드에 있는 이모티콘 개수를 화면에 붙여넣기 위해

말 그대로 화면에 있는 이모티콘 개수와 클립보드의 이모티콘 개수를 더해주면 된다.

visited[screen + clip][clip]를 방문하지 않았을 경우 (-1) 현재 위치(visited[screen][clip]) 값에서 1을 더해준 값을 visited[screen + clip][clip] 위치에 할당한다.

즉, 위 코드에서 시작 좌표값에 0 + 1을 해준 상태이므로 2의 값이 할당된다.

 

또한, 화면과 클립보드의 이모티콘 개수가 S를 넘지 않을 경우로 범위를 지정해준다.

 

 

화면에 있는 이모티콘 개수 1개 지우기

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

이 구문은 위 2개의 if문 실행 후 실행되는 구문이다.

화면에서 하나의 이모티콘을 빼고자 방문 리스트에서 screen값에 1을 빼준 인덱스 값이 -1일때 (방문하지 않았을 때) 

화면의 이모티콘 개수 값을 하나 뺀 후 queue에 값을 넣어준다. 

 

 

위 구문들을 모두 수행한 후 screen이 S의 개수와 같아진다면 

    if screen == S:
            print(visited[screen][clip])
            break

이 구문을 실행하게 되고 S까지 도달한 시간을 출력하게 된다.