최악의 경우는 대략 이런 경우를 생각해볼 수 있을 것 같습니다. 대략 전체의 반 정도를 지그재그 모양으로 1 차이로 이어줍니다. 그 후 이로부터 계속 가지를 치면서 더 작은 값들을 주변에 이어나갑니다. 서로 다른 방향으로 나간 값들끼리는 이후 만나지 않도록 합니다. 그러면 가지가 생긴 개수만큼의 시작점이 생기고, 그 값들은 경로를 따라 올라간 뒤 마지막 지그재그를 다 돌아야 합니다. 그러면 지그재그의 크기가 O(N^2)이고, 가지를 쳐서 마지막에 남게 되는 시작점의 개수도 O(N^2)개를 만들 수 있을 테니, 총 O(N^4)이 되는 것을 피할 수 없게 됩니다.

또한 이 코드는 답도 틀릴 것 같습니다. BFS는 최'단'거리를 구하는 알고리즘이기 때문에, 이 문제와 같이 최'장'거리를 구하는 데에는 반례가 있습니다. 더 멀리 돌아서 가는 것이 이득일 수 있는데, 옆에 있다면 무조건 바로 방문해버리기 때문입니다.

일반적으로 지금과 같이 '많이 커트될 것 같은' 것은 정해가 아니고, 잘 먹히는 경우도 드뭅니다. 점근적으로 시간 복잡도를 줄일 수 있는지를 항상 증명하도록 연습하는 것이 좋습니다.

자꾸 시간복잡도를 제대로 따지지 않고 감으로 알고리즘을 짜는 경향이 꽤 있는 것 같습니다.

그래프 탐색 개념도 제대로 모르고 기계적으로 쓰고 있었던것 같네요.. 정말 감사합니다!!