백준 14226번 이모티콘 | python | bfs

문제

링크

풀이

최단시간을 구하는 것이니 해당 문제 또한 bfs로 풀어주면 된다.
이전 숨바꼭질 문제들과 다른 점은 visited 배열이 2차원으로 생성된다는 점인데 현재 화면에 나와있는 이모티콘 개수가 동일하더라도 클립보드에 저장되어있는 이모티콘 개수에 따라 연산 과정이 달라지기 때문이다.

따라서 가로행은 화면에 있는 이모티콘 개수, 세로행은 클립보드에 있는 이모티콘 개수라고 가정하여 방문 여부 및 이모티콘 개수(화면,클립)별 최소 시간을 갱신하는 2차원 배열의 visited를 만든다.

bfs 실행 과정은 이전 방식과 동일하며, 큐에 원소를 삽입할 때에도 현재 화면에 존재하는 이모티콘 개수, 현재 클립보드에 저장된 이모티콘 개수를 튜플 형태로 저장해야한다는 점만 유의하면 된다.

import sys
from collections import deque
from pprint import pprint

input = sys.stdin.readline

s = int(input().strip())
visited = [[0] * 1001 for _ in range(1001)]  # 카운트 세는 리스트


def bfs():
    q = deque()
    ans = 0
    q.append((1, 0))  # (화면에 존재하는 이모티콘 개수,현재 클립보드에 저장된 이모티콘 개수)
    while q:
        x_screen, x_clip = q.popleft()
        if x_screen == s:
            ans = visited[x_screen][x_clip]
            break

        arr = [
            (x_screen, x_screen),
            (x_screen + x_clip, x_clip),
            (x_screen - 1, x_clip),
        ]

        for screen, clip in arr:
            if 0 <= screen < 1001 and 0 <= clip < 1001 and not visited[screen][clip]:
                # 첫 번째 경우
                q.append((screen, clip))  # 현재 화면에 존재하는 이모티콘 개수 만큼 클립보드에 저장
                visited[screen][clip] = visited[x_screen][x_clip] + 1

    return ans


print(bfs())