이 방법과 똑같은 방법으로 풀다가 틀리신 분을 봤었는데, 반례가 매우 드물게 있고 손으로 계산 가능한 정도가 아니기 때문에 반례를 알려드리는 것은 크게 의미가 없을 것 같습니다. 하나 드리자면, 872에 대한 정답은 22이지만 이 코드는 23을 출력합니다.

기본적으로 BFS는 "현재 상태"를 나타내는 모든 변수들이 전부 개별적으로 고려되어야 합니다. 지금 코드를 보면, 횟수를 나타내는 cnt를 제외하고 num과 clipboard라는 2개의 변수를 큐에 담고 있음에도 불구하고 방문 체크는 오로지 num에 대해서만 하고 있습니다. 이렇게 하면 최적해가 나오지 않을 수 있습니다.

예를 들어 A라는 수의 이모티콘을 화면에 최대한 빨리 출력하는 순간에 클립보드에는 B개의 이모티콘이 담겨있다고 해봅시다. 그런데 A개의 이모티콘을 화면에 출력하는 데에는 더 오랜 시간이 걸리지만 이 때 C개의 이모티콘이 클립보드에 담겨있는 경우 D개를 화면에 출력하는 시간을 더 단축하는 경우가 있을 수 있습니다. 이 코드는 그런 경우를 처리하지 못합니다. A개를 출력하는 순간 C개의 이모티콘이 클립보드에 담긴 상황을 이미 배제해버리기 때문입니다.

그래서 이런 문제에 대해 정확한 BFS를 구현하려면 num과 clipboard 값 둘 다를 모두 고려해야 합니다. visited[num][clipboard]와 같이 사용하도록 해야 합니다. 이 문제 뿐만 아니라, 어떠한 BFS든 서로 종속적이지 않은 변수들을 큐에 넣어야 한다면 방문 체크 역시 각각을 별개의 차원으로 놓고 해야 합니다.

친절한 설명에 감사드립니다.

그런데 제가 아직 이해를 하지 못해서 질문을 한 번 더 드려도 될까요?

제가 이해력이 부족하여 예를 들어주신 부분이 무슨 말씀이신지 잘 이해가 되지 않습니다. 한 번만 더 설명해주실 수 있을까요?

이 문제가 고려하는 것은 S개의 이모티콘이 화면에 출력되는 경우를 찾는 것인데 왜 굳이 클립보드에 있는 이모티콘까지 방문 체크를 고려하는 것인지 이해가 잘 되지 않습니다.

그리고 제 생각에 클립보드의 방문 체크를 하지 않는다면 클립보드에 대해서는 브루트 포스를 진행하는 것인데 그렇다면 모든 경우의 수를 고려하는 것이므로 역시 최적해가 나와야하지 않나요??

다시 한 번 친절한 설명에 감사드립니다.

클립보드에 대해서 브루트 포스가 진행되지 않습니다. 예를 들어 (진짜로 이렇지는 않지만) 100이라는 수가 화면에 출력되게 하기 위해 최적인 경우가 화면 70, 클립보드 30인 상태에서 붙여넣기로 화면 100, 클립보드 30을 만드는 것이고 이 때까지 최소 횟수가 10회였다고 해봅시다. 이 때 visited[100] = true가 됩니다. 그리고 이렇게 한 상태에서 다시 200개를 화면에 출력하기 위해 필요한 추가 횟수가 10회라고 가정해봅시다. 그러면 이 경로를 거쳐서 200개를 화면에 출력하는 최소 횟수는 총 20회입니다.

그런데 만일 100개를 화면에 출력하는 데에 10번이 아니라 11번이 걸리지만 이 때 클립보드에 50개가 담겨있게 할 수 있다고 해봅시다. 그러면 200개를 화면에 출력하려면 여기서 붙여넣기 2번만 더 하면 되므로 200개를 출력하는 데에는 13회면 충분합니다. 그런데, 10회에서 visited[50+50]을 보는 순간 이미 visited[100]에는 true가 들어있어, 11회째에 100을 방문하는 게 불가능해집니다. 그래서 100개에서 손해를 좀 더 보면 추후에 훨씬 나은 결과를 얻을 수 있음에도 불구하고 그런 경우를 고려하지 못하게 됩니다.

아 그렇군요!

명쾌하신 설명에 이해가 되었습니다. 정말 감사합니다!!!