백준 14226 이모티콘(python)

문제

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

14226번: 이모티콘

---

주어진 경우에 맞게 연산들을 진행해 나가며 목표 개수에 도달하는 문제입니다. BFS 방식으로 접근하였습니다. 과정은 다음과 같습니다.

• 각 경우로 조건을 나누어서 연산을 진행해 줍니다.
• 연산된 결과를  통해 이전에 접근했는지를 확인해줍니다. 가보지 않은 경우라면 큐에 넣어주고 과정을 진행합니다.
• 최종적으로 목표 개수에 도달하면 시간값을 출력해 줍니다.

확인 리스트를 2차원으로 한 이유는 화면에 있는 숫자 상황만 체크하면 넘어가는 경우가 있기 때문입니다.

---

소스코드 

import sys
from collections import deque

input = sys.stdin.readline

q = deque()
MAX = 1001
S = int(input())
q.append((1, 0, 0))  # 화면개수, 클립보드, 시간
ch = [[0]*MAX for _ in range(MAX)]
while q:
    tmp = q.popleft()

    if tmp[0] == S:  # 목적 개수 달성하면 출력
        print(tmp[2])
        break

    if ch[tmp[0]][tmp[0]] == 0:  # 클립보드에 개수 복사
        ch[tmp[0]][tmp[0]] = 1
        q.append((tmp[0], tmp[0], tmp[2]+1))

    if tmp[1]+tmp[0] < MAX and ch[tmp[0]+tmp[1]][tmp[1]] == 0:  # 화면에 클립보드에 있는 개수 붙여넣기
        ch[tmp[0]+tmp[1]][tmp[1]] = 1
        q.append((tmp[0]+tmp[1], tmp[1], tmp[2]+1))

    if tmp[0]-1 > 0:  # 화면 이모티콘 개수 하나 빼기
        if tmp[0] < MAX and ch[tmp[0]-1][tmp[1]] == 0:
            ch[tmp[0]-1][tmp[1]] = 1
            q.append((tmp[0]-1, tmp[1], tmp[2]+1))