[백준]14226번 이모티콘 파이썬 python

문제링크

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

14226번: 이모티콘

코드

import sys
from collections import deque
 
input = sys.stdin.readline
MAX = 2000
 
target = int(input())
 
def bfs(target):
    dq = deque()
    visited = [[-1]*MAX for _ in range(MAX)] #화면,클립보드 방문횟수
    s = 1 #화면
    c = 0 #클립보드
    dq.append((s,c))
    visited[s][c]=0
    while dq:
        s,c = dq.popleft()
        #target과 일치
        if s==target:
            print(visited[s][c])
            break
 
        # action1 화면-> 클립보드
        nc = s
        if 0<=s<MAX and 0<=nc<MAX and visited[s][nc]==-1:
            visited[s][nc]=visited[s][c]+1
            dq. append((s,nc))
 
        # action2 클립보드 -> 화면
        ns = s + c
        if c!=0 and 0<=ns<MAX and 0<=c<MAX and visited[ns][c]==-1:
            visited[ns][c]= visited[s][c]+1
            dq.append((ns, c))
        #action3 화면 -1
        ns = s - 1
        if s>0 and 0<=ns<MAX and 0<=c<MAX and visited[ns][c]==-1:
            visited[ns][c] = visited[s][c]+1
            dq.append((ns, c))
 
bfs(target)

핵심Point

* BFS로 풀 수 있는 이유 : 가중치가 같은 최단경로 문제 유형
노드 : 화면에 있는 현재 이모티콘 수
간선 : 문제에서 정의한 3가지 action
이때, 마지막 action인 화면에서 -1은 화면 값이 목표값보다 커졌을때만 필요한가? 라는 생각이 들었지만 아닌 경우도 있다.

* 화면과 클립보드를 어떻게 표현할 것인가
해결)이모티콘 갯수 정보만 필요한 것 이므로 변수로 표현한다.
      이때, 화면 업데이트시 그 당시의 클립보드 수가 필요하므로 (#화면, #클립보드)의 쌍으로 정보를 저장한다.