[#14226] 이모티콘

문제

#14226 이모티콘
Gold4
적용 알고리즘: BFS 알고리즘

---

풀이 방법

• BFS 알고리즘을 사용하여 최소의 값을 구한다.
• 화면의 이모티콘 수, 클립보드 상태의 방문 상태를 확인하는 2차원 리스트를 생성한다.
• deque 자료구조를 사용하고, 화면의 이모티콘 수와 클립보드의 상태, 작업시간을 저장한다.
• 화면의 이모티콘은 최대 1000개까지 입력할 수 있고, 이 경우 복사를 진행하게 되면 클립보드의 이모티콘 개수는 1000개가 가능하다. 클립보드의 이모티콘을 화면에 붙여넣기 하면 화면의 이모티콘 개수는 최대 2000개가 가능하므로 방문 여부를 확인하는 리스트는 2001개로 지정해준다.

코드 흐름

1. 숫자를 입력받고, 방문 리스트를 생성한다.
2. 덱에 초기 상태인 [1, 0, 0]을 집어넣는다.
3. 덱에서 가장 첫 번째 항목을 꺼내 아래의 세 가지 과정을 수행한다.
4. [1. 복사] 화면의 이모티콘의 개수가 1개 이상, 1000개까지 있을때 수행한다. 이때 클립보드의 수는 현재 화면의 이모티콘의 수와 동일해지므로 visited[emoji][emoji]의 방문 여부를 확인한다. 방문하지 않았다면, 이를 방문상태로 전환해주고 복사했을 때의 상태를 덱에 집어넣는다.
5. [2. 삭제] 마찬가지로 화면의 이모티콘의 개수가 1개 이상, 1000개까지 있을때 수행한다. 이때 화면의 이모티콘 수는 현재 화면의 이모티콘의 수에서 하나가 삭제된 상황이므로 visited[emoji - 1][clip]의 방문 여부를 확인한다. 이후 4와 마찬가지로 방문여부를 변환하고, 덱에 집어넣는다.
6. [3. 붙여넣기] 클립보드에 남아있는 이모티콘의 수가 1개 이상, 1000개 이하일때, 또한 이를 붙여넣었을 때의 화면의 이모티콘 수(emoji + clip)가 2000개 이하일 때 수행한다. 이때 화면의 이모티콘의 수는 현재 클립보드의 이모티콘 수, 현재 화면의 이모티콘을 더한 수이므로 visited[emoji + clip][clip]의 방문 여부를 확인한다. 뒷 과정은 4와 동일하다.
7. 현재 화면의 이모티콘 수가 입력된 이모티콘의 수와 동일해질 때까지 4-6과정을 수행한다. 동일하다면, 현재까지의 작업시간을 화면에 출력하고 루프를 빠져나온다.

코드

from collections import deque


s = int(input())
visited = [[False for _ in range(2001)] for _ in range(2001)]

status = deque()
status.append([1, 0, 0])

while(status):
    emoji, clip, time = status.popleft()

    if (emoji == s):
        print(time)
        break
    
    if (0 < emoji <= 1000):
        # 복사
        if (visited[emoji][emoji] == False):
            visited[emoji][emoji] = True
            status.append([emoji, emoji, time + 1])
        # 삭제
        if (visited[emoji - 1][clip] == False):
            visited[emoji - 1][clip] = True
            status.append([emoji - 1, clip, time + 1])
        
    # 붙여넣기
    if (0 < clip <= 1000 and 0 < emoji + clip <= 2000):
        if (visited[emoji + clip][clip] == False):
            visited[emoji + clip][clip] = True
            status.append([emoji + clip, clip, time + 1])

체감 난이도: 4.8/5
처음 문제를 접했을 때에는 문제 이해는 되었지만 이를 어떻게 BFS 알고리즘을 적용해서 푸는것인지 막막했다. 이곳저곳 참고를 많이 해서 문제를 풀었는데, 생각보다 코드가 간결해서 놀랐다. 문제를 푸는 과정에서 Out Of Index 에러가 나서 고생을 좀 했었다. 이 문제를 풂으로써 비슷한 유형도 도전해보고 싶어졌다. 솔직히 미 문제는 이 알고리즘을 쓰는 것이다~ 라고 미리 알고 있었기에 알고리즘을 적용하는 에 중점을 두어 문제를 풀었지만 이 정보도 없었으면 너무 막막했을 문제다. 처음 그 알고리즘을 사용해서 문제를 푸는것이다 라는 것을 알았음에도 불고하고 이게 대체 어떻게 쓰이는 거지라는 생각이 들었으니 말이다… 앞으로는 이런 최단거리를 구하는 문제는 BFS 알고리즘을 우선 적용해서 문제를 접근하도록 노력해야겠다.