[백준/Python] 14226. 이모티콘

14226. 이모티콘

14226번: 이모티콘

• BFS

처음 접근은 DP로 했었다.

S만큼의 2차원 배열을 선언할 수 있고, 1,2,3번을 수행하기 이전의 값+1을 이후 경우에
점진적으로 대입해주면 된다고 생각했기 때문이다.

하지만 이 문제는 단순히 DP로 풀기 어렵다.

DP로 풀기 어려운 이유

탐색할 수가 점진적으로 증가하는 것이 아니라, 무작위로 증가 또는 감소하게 된다.

DP는 값의 갱신이 단방향으로 일어나기 때문에, 증가/감소가 함께 일어나는 탐색에서 사용할 수 없다.

따라서 이 문제는 최단거리 문제로 접근하는 것이 좋다.

우선순위 큐를 사용하지 않아도 되는 이유

하지만 다익스트라 등을 도입할 필요는 또 없다.

이 문제에서 가중치는 점진적으로 증가하기 때문이다. (모든 동작에 대하여 가중치(time)이 1씩 증가)

따라서 Priority Queue를 사용할 필요는 없으며, Queue를 이용하는 BFS로 풀이할 수 있다.

코드 (Python)

import sys
from collections import deque
input = sys.stdin.readline

s = int(input())
MAX = 2*(s-1)
visited = [[False]*(MAX+1) for _ in range(MAX+1)]
q = deque([(1, 0, 0)])
while q:
    screen, board, time = q.popleft()
    if screen == s:
        print(time)
        break
    if not visited[screen-1][board]: # case 3
        visited[screen-1][board] = True
        q.append((screen-1, board, time+1))
    if screen > s: # 이 경우, case 3 이외에는 고려할 필요 없음
        continue
    if 0 < screen < s and not visited[screen+board][board]: # case 1
        visited[screen+board][board] = True
        q.append((screen+board, board, time+1))
    if not visited[screen][screen]: # case 2
        visited[screen][screen] = True
        q.append((screen, screen, time+1))