[BOJ14226 이모티콘] BFS (Python)

문제조건

• 화면 이모티콘 개수는 클립보드 이모티콘 개수에 따라 달라진다.

핵심개념

• BFS에서 하나의 정점이 여러 개의 정보를 갖고 있으면 안 된다.
• 화면 이모티콘 개수는 클립보드 이모티콘 개수에 따라 정보가 달라진다.
• 클립모드 이모티콘 개수를 기준으로 나눠서 BFS를 사용한다.

코드

from collections import deque

n = int(input())

dist = [[-1]*1001 for _ in range(1001)]

q = deque()
q.append((1, 0))
dist[1][0] = 0

while q:
    s, c = q.popleft()
    # (1) 화면 이모티콘을 클립보드에 복붙
    if dist[s][s] == -1:
        q.append((s, s))
        dist[s][s] = dist[s][c] + 1
    # (2) 클립보드 이모티콘을 화면에 복붙
    if s+c <= n and dist[s+c][c] == -1:
        q.append((s+c, c))
        dist[s+c][c] = dist[s][c] + 1
    # (3) 화면 이모티콘 1개 삭제
    if s-1 >= 0 and dist[s-1][c] == -1:
        q.append((s-1, c))
        dist[s-1][c] = dist[s][c] + 1

ans = 1000
for i in dist[n]:
    if i == -1 :
        continue
    else:
        ans = min(ans, i)

print(ans)

 

 

from collections import deque
 
def bfs(emo):
    global n
    queue = deque()
    queue.append(emo)
    time[emo[0]][emo[1]] = 0
    while queue:
        s, c = queue.popleft()
        for cmd in [(s,s), (s+c,c), (s-1,c)]:
            if 0<=cmd[0]<=n and time[cmd[0]][cmd[1]] == -1:
                time[cmd[0]][cmd[1]] = time[s][c]+1
                queue.append(cmd)
            # 화면에 원하는 이모티콘 개수가 있으면 탐색을 종료한다.
            if cmd[0] == n:
                return time[cmd[0]][cmd[1]]
            
n = int(input())
time = [[-1]*(n+1) for _ in range(n+1)]
answer = bfs((1,0))
print(answer)

3가지 연산을 배열로 만들어서 한 번에 비교하는 코드