백준 14226번 - 이모티콘 (Python)

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

14226번: 이모티콘

생각해보기

매 시행마다 세 가지 연산 중 하나를 수행하며, S개의 이모티콘을 만드는데 걸리는 최소 시간을 구한다.

이모티콘의 개수와 클립보드 둘 다 고려해야 한다.

 

BFS로 어떻게 탐색하게 할 것인가?

방문 체크를 세 가지 연산과 함께 고려한다.

 

풀이 1) 방문 체크를 2차원 배열로 하기

import sys
from collections import deque

input = sys.stdin.readline

s = int(input())

q = deque()
q.append((1, 0))

visited = [[-1] * (s + 1) for _ in range(s + 1)]
visited[1][0] = 0

while q:
    emote, clip = q.popleft()
    
    if (emote == s):
        print(visited[emote][clip])
        break

    if (visited[emote][emote] == -1):
        visited[emote][emote] = visited[emote][clip] + 1
        q.append((emote, emote))

    if (emote + clip) <= s and (visited[emote + clip][clip] == -1):
        visited[emote + clip][clip] = visited[emote][clip] + 1
        q.append((emote + clip, clip))

    if (emote - 1) >= 0 and (visited[emote - 1][clip] == -1):
        visited[emote - 1][clip] = visited[emote][clip] + 1
        q.append((emote - 1, clip))

방문 체크 리스트의 크기를 이모티콘의 목표 개수에 맞춰 설정하였으므로, IndexError가 나지 않도록 범위를 조건에 추가한다.

 

풀이 2) 방문 체크를 딕셔너리로 하기

import sys
from collections import deque

input = sys.stdin.readline

s = int(input())

q = deque()
q.append((1, 0))

visited = dict()
visited[(1, 0)] = 0

while q:
    emote, clip = q.popleft()
    if (emote == s):
        print(visited[(emote, clip)])
        break

    if (emote, emote) not in visited.keys():
        visited[(emote, emote)] = visited[(emote, clip)] + 1
        q.append((emote, emote))

    if (emote + clip, clip) not in visited.keys():
        visited[(emote + clip, clip)] = visited[(emote, clip)] + 1
        q.append((emote + clip, clip))

    if (emote - 1) >= 0 and (emote - 1, clip) not in visited.keys():
        visited[(emote - 1, clip)] = visited[(emote, clip)] + 1
        q.append((emote - 1, clip))