[백준 14226번] 이모티콘 - python

문제 링크

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

14226번: 이모티콘

 

풀이 

- bfs 풀이

큐에 ( 화면에 있는 이모티콘 개수, 클립모드에 있는 이모티콘 개수, 연산 횟수)를 넣어주고 

bfs 를 실행한다. 

visited[화면개수][클립보드개수]로 방문 표시를 한다. 

화면에 있는 이모티콘 개수가 s와 같으면 연산 횟수 return 

1. 클립보드에 저장할 경우 방문하지 않았으면 

큐에 (화면개수, 화면개수, 연산횟수 +1)을 넣어주고 방문 표시 

2. 화면에 붙여넣기 할 경우 방문하지 않았으면 

큐에 (화면개수 + 클립보드개수, 클립보드개수, 연산횟수 +1) 을 넣어주고 방문 표시 

3. 하나 삭제할 경우 방문하지 않았으면 

큐에 (화면개수-1, 클립보드개수, 연산횟수 +1)을 넣어주고 방문 표시하면 된다. 

from collections import deque 

def bfs():
    
    q = deque()
    # visited[화면 개수][클립보드 개수] 방문 표시 
    visited = [ [0] * (s+1) for _ in range(s+1) ] 
    visited[1][0] = True
    # (화면개수, 클립보드개수, 연산횟수 )
    q.append((1,0,0))
    
    while q :
        screen, board, cnt = q.popleft()
        
        # 화면에 있는 이모티콘 개수가 s개 이면 연산횟수 리턴 
        if screen == s :
            return cnt 
            
        # 클립보드에 저장 
        if not visited[screen][screen] :
            q.append((screen,screen, cnt+1))
            visited[screen][screen] = True
            
        # 화면에 붙여넣기 
        if screen + board < s+1 :
            if not visited[screen + board][board] :
                q.append((screen +board, board, cnt + 1))
                visited[screen+board][board] = True 
        
        # 화면의 이모티콘 하나 삭제하기 
        if screen -1 >= 0:
            if not visited[screen-1][board] :
                q.append((screen-1, board ,cnt +1))
                visited[screen-1][board] = True       
                
    return -1  
        
s = int(input())
print(bfs())

원래 처음에는 배열 크기를 1001 만큼 선언해주었는데, 런타임 에러가 발생하였다. 

크기를 s+1로 변경해주니 해결되었는데 왜 ?