14226번 이모티콘 백준 파이썬

문제:www.acmicpc.net/problem/14226

14226번: 이모티콘

고려해야 할 것은 다음과 같다.

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

이 세가지를 유의하여 방문을 하면 된다.

 

import sys
from collections import deque
S=int(input())
visited=[[-1]*3001 for _ in range(3001)]
 
def bfs(left,right):
    q=deque()
    q.append([left,right])
    visited[left][right]=0
    while q:
        emoti,clip=q.popleft()
        if emoti==S:
            break
        if clip:
            if visited[emoti+clip][clip]==-1 and emoti+clip<=S:
                visited[emoti+clip][clip]=visited[emoti][clip]+1
                q.append([emoti+clip,clip])
 
            if visited[emoti][emoti]==-1:
                q.append([emoti,emoti])
                visited[emoti][emoti]=visited[emoti][clip]+1
 
            if visited[emoti-1][clip]==-1 and emoti-1>0:
                visited[emoti-1][clip]=visited[emoti][clip]+1
                q.append([emoti-1,clip])
        else:
            q.append([emoti,emoti])
            visited[emoti][emoti]=visited[emoti][clip]+1
        
bfs(1,0)
ans=10e9
for i in range(S+1):
    if visited[S][i]!=-1:
        ans=min(ans,visited[S][i])
print(ans)

화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한 방법은 if문 2번째, 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한 것은 1번째, 화면에 있는 이모티콘 중 하나를 삭제하는 것은 마지막이다.

else는 처음에 1이 아니면 무조건 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장하는 것이다.

 

이 문제를 풀면서 bfs문제 보다는 완전탐색의 느낌을 많이 느꼈던 문제 였다.