아닙니다. 말씀하신 것은 애초에 BFS의 정의에 맞지 않는 탐색 방법입니다. BFS는 무조건 큐에 들어간 순서대로 뽑아야 하는 것이고, 이미 큐에 들어가있는데 나중에 더 정점 번호가 작은 것이 들어왔다고 해서 자리가 바뀌어야 하는 것이 아닙니다. 큐에 들어온 순서대로 뽑는 것은 정해져 있는 것이며, 그 조건 내에서 가능한 정점 번호가 작은 것부터 뽑아야 하므로 큐에 넣을 때만 정점 번호가 작은 순서대로 넣으면 됩니다.

큐의 맨 앞에 원소를 끼워넣을 수 없습니다.

만약에 모호한 점이 있을 수 있다면 BFS라는 용어 자체에는 큐를 써야 한다는 말이 없기 때문에 거리가 같다면 큐에 들어간 순서가 아닌 순서로도 뺄 수 있다고 생각할 수 있는데, 그러면 그러한 조건이 추가되면 될 것 같습니다.

BFS는 무조건 큐에 들어간 순서가 아닙니다. BFS를 구현함에 있어 현재 단계와 다음 단계는 나누어져 있지만 현재 단계에서 어떤 원소를 택하는지는 정의되어 있지 않습니다. BFS는 단지 단계에 대하여 DFS일 뿐입니다.

BFS는 다음 깊이로 이동하기 전 현재 깊이의 모든 이웃을 먼저 탐색하는 방법입니다. BFS의 구현은 보통 큐가 간단하고 효율적이라 많이 사용되지만 큐를 전혀 사용하지 않고 스택과 재귀로도 충분히 구현 가능합니다. BFS는 오로지 큐를 사용한 구현체로서 정의되지 않습니다.

그래서 저는 조건 추가를 주장하는 바입니다. 문제의 정의가 모호하지만 채점이 그 의도를 말해주고 있으니 지문이 바뀌는 게 합리적입니다.

원글 작성하신 분의 주장은 옳은 문제 제기입니다. 문제의 의도가 BFS로 너비를 구한 이후 추가적인 정렬을 원하는 것은 아니기 때문에, 지문을 수정하는 것이 좋겠습니다.

다만 지문을 의도대로 바꾸는 것이 상당히 까다로울 것으로 보입니다. 문제의 의도에 맞게 지문을 수정하면 다음과 같습니다.

정점 V와 연결된 정점 n에 대해 n의 너비를 주어진 정점 V로부터의 최단 거리로 정의한다. 이때 BFS에 대해서는 출력된 순서가 다음을 만족해야 한다.

• 출력된 정점 n은 모두 V와 연결되어 있어야 한다.
• 정점 n의 너비가 정점 m의 너비보다 작다면, n은 m보다 먼저 출력되어야 한다.
• 서로 같지 않은 정점 n의 너비와 정점 m의 너비가 b로 같고, 정점 n과 간선으로 직접 연결된 모든 너비 b - 1의 정점 중 가장 먼저 출력된 정점이 정점 m과 간선으로 직접 연결된 모든 너비 b - 1의 정점 중 가장 먼저 출력된 정점보다 먼저 출력되었다면, n은 m보다 먼저 출력되어야 한다.
• 서로 같지 않은 정점 n의 너비와 정점 m의 너비가 b로 같고, 정점 n과 간선으로 직접 연결된 모든 너비 b - 1의 정점 중 가장 먼저 출력된 정점이 정점 m과 간선으로 직접 연결된 모든 너비 b - 1의 정점 중 가장 먼저 출력된 정점과 같으며, n의 정점 번호가 m의 정점 번호보다 작으면, n은 m보다 먼저 출력되어야 한다.

위 조건을 만족하는 순서의 존재성과 유일성이 보장된다.

이 지문 자체는 정확하지만 아무래도 초심자 분들이 문제를 그냥 풀기에는 매우 난해한 설명으로 보이니, 노트 정도에 "큐를 이용해서 BFS를 짤 때, 정점 번호를 작은 것부터 순서대로 넣으면 문제의 조건을 만족하는 순서를 출력할 수 있다." 정도의 문장을 넣는 것이 좋아 보입니다.

제 생각에는 조건을 추가하는 것이 맞을 거 같네요. 옛날에 다른 문제들은 문제가 뜻하는 바를 이해라도 할 수 있는데, 이 문제는 문제가 뜻하는 바도 이해하지 못하겠어서 당황했던 기억이 있네요. 문제에서의 DFS와 BFS의 방식에 대해 적어두는 것이 좋을 거 같습니다.

초심자용 문제인 만큼, 지문 수정을 해야 한다면 출력 조건보다는 작동 방식을 상세하게 적는 것이 낫다고 생각합니다.

정리해주세요.