[백준 14226] 이모티콘 - Python (BFS, DP)

 

14226번: 이모티콘

 

 

<내 코드>

 

from collections import deque


def bfs():

    while q:
        s, c = q.popleft()
        # 복사, 붙여넣기, 삭제 후 1초씩 증가 && 다녀간 곳 q에 추가
        # 복사
        if check[s][s] == -1:
            check[s][s] = check[s][c] + 1
            q.append((s, s))
        # 붙여넣기
        if s+c <= S and check[s+c][c] == -1:
            check[s+c][c] = check[s][c] + 1
            q.append((s+c, c))
        # 삭제
        if s-1 >= 0 and check[s-1][c] == -1:
            check[s-1][c] = check[s][c] + 1
            q.append((s-1, c))


S = int(input())
q = deque()
MAX = 1001
check = [[-1]*MAX for _ in range(MAX)]

check[1][0] = 0
q.append((1, 0))

bfs()

ans = -1
for i in range(S):
    if check[S][i] != -1:
        if ans == -1 or ans > check[S][i]:
            ans = check[S][i]
print(ans)

 

처음에 문제를 복사 - 붙여 넣기 - 복사- 붙여 넣기... 하는 것으로 잘못 이해했었다. 실제로는 클립보드에 들어있는 이모티콘은 여러 번 화면에 붙여 넣기가 가능한 것이다.

이 문제는 기존의 BFS 문제랑 조금 차이가 있다. 기존에는 입력을 그래프 형태로 주어졌는데, 이 문제는 본인이 새로 그래프를 만들어야 했다. 복사, 붙여넣기, 삭제 부분을 작성하고 현재 s,c에 대한  시간 check [s][c] 값에 +1초씩 해준다.  그리고 찾고자 하는 입력 값 check [s] 중 최솟값을 찾아 출력하면 된다.