백준 14226번 파이썬 문제풀이(BFS - 이모티콘)

---

이 문제는 답을 보고도 생각하는데 오래 걸렸던 문제이다. 문제의 핵심은 bfs를 돌기위하여 방문 처리를 이중리스트로 만드는 것이 핵심이다. 즉, visited[화면이모티콘 개수][클립보드 이모티콘 개수] 로 설정하여 각각의 경우마다 방문처리를 해주어야 한다는 것이다. 또한 이모티콘 개수가 범위를 벗어나지 않도록 범위처리를 해주는것도 핵심이다.

 

from collections import deque

S = int(input())

queue = deque([[1, 0, 0]])  # 화면의 이모티콘 개수, 클립보드 이모티콘 개수, 연산 횟수

visited = [[False] * 1001 for _ in range(1001)]
visited[1][0] = True

while queue:

    screen, clipboard, cnt = queue.popleft()

    if screen == S:  # 만약 스크린의 개수와 S가 동일하다면
        print(cnt)  # 걸린 횟수를 출력 후
        break  # 탈출

    for i in range(3):  # 연산을 3번 수행한다.

        # 화면에 있는 이모티콘을 복사해서 클립보드에 저장
        if i == 0:
            new_clipboard, new_screen = screen, screen

        # 화면에 클립보드에 있는 이모티콘 들을 추가
        elif i == 1:
            new_screen, new_clipboard = screen + clipboard, clipboard
            
        # 화면에 있는 이모티콘 개수 한개 빼기
        else:
            new_screen, new_clipboard = screen - 1, clipboard

        # 만약 새로 계산된 이모티콘과 클립보드의 개수가 범위를 벗어나거나 이미 방문한 적이 있다면 continue
        if new_screen >= 1001 or new_screen < 0 or new_clipboard >= 1001 or new_clipboard < 0 or visited[new_screen][
            new_clipboard]:
            continue

        # 방문처리 후 연산 횟수를 +1 하여 큐에 추가
        visited[new_screen][new_clipboard] = True
        queue.append([new_screen, new_clipboard, cnt + 1])