[BOJ]14226 - 이모티콘 (Python)

문제 

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

코드 

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()


def bfs(s, c):
    queue = deque()
    queue.append((s, c))
    while queue:
        s, c = queue.popleft()
        if dist[s][s] == -1:   #방문하지 않은 경우, 화면에서 클립보드로
            dist[s][s] = dist[s][c] + 1
            queue.append((s, s))
        if s+c <= n and dist[s+c][c] == -1:   #클립보드에서 화면으로
            dist[s+c][c] = dist[s][c] + 1
            queue.append((s+c, c))
        if s-1 >= 0 and dist[s-1][c] == -1:   #삭제
            dist[s-1][c] = dist[s][c] + 1
            queue.append((s-1, c))


n = int(input())
dist = [[-1] * (n+1) for _ in range(n+1)]
dist[1][0] = 0     #1차 인덱스는 화면, 2차 인덱스는 클립보드
bfs(1, 0)

answer = -1
for i in range(n+1):
    if dist[n][i] != -1:
        if answer == -1 or answer > dist[n][i]:
            answer = dist[n][i]
print(answer)

 

풀이 

문제집에서 BFS로 분류되어 있었지만 어떻게 풀어야 할 지 몰랐다 

답을 보고 2차원 배열을 화면에 있는 이모티콘 수(s)와 클립보드에 있는 이모티콘 수(c)로 만들어야 한다는 것을 알았다

저번에 풀었던 숨바꼭질 문제와 유사하다는 생각이 들었다 (같은 유형이라서 그런듯) 

다음에도 비슷한 문제를 풀게 된다면... 

 

• 그래프 형태가 주어지지 않은 경우 내가 직접 만들어 본다 
• 답을 보기 전에 조금만 더 생각해보자 
• 배열의 원소로 시간 등의 값을 넣는게 따로 변수를 빼는 것보다 효율적이다