DFS와 BFS 모두 틀렸습니다. 둘을 한 번에 틀리게 만드는 반례는 다음과 같습니다.
4 3 2
2 3
3 1
1 2
정답은
2 1 3
2 1 3
이어야 하나,
2 1 3 3
2 3 1
이 출력되고 있습니다.
이 코드에서 문제점을 찾자면 상당히 많습니다. 단순히 맞고 틀리고를 떠나서, 군데군데의 설계가 상당히 비효율적입니다.
우선 DFS에서 틀린 곳은 40번째 줄인데, 모든 정점이 연결되어 있다는 보장이 없으므로 len이 N이 되지 않더라도 더이상 방문할 수 있는 정점이 없다면 탐색을 종료해야 합니다. 하지만 지금 코드는 3이 visited에 2번 추가되기 때문에 마지막에 3을 한 번 더 방문하여 4개를 채우고서야 종료됩니다. 중복 방문이 일어날 수 있기 때문에, 이미 방문한 정점이라면 다시 방문하지 않도록 방지해야 합니다.
BFS에서 틀린 곳은 간선이 정렬된 순서로 들어오지 않을 수 있다는 점입니다. 입력된 순서로 저장해 두니, 2에서 3을 가는 간선과 1을 가는 간선이 모두 있다면 먼저 입력된 3 쪽이 먼저 큐에 들어갑니다. 그러나 문제에는 "방문할 수 있는 정점이 여럿인 경우 더 작은 번호의 정점을 먼저 방문한다"고 되어 있습니다.
여기엔 매우 매우 비효율적인 코드가 여럿 있습니다. 19번째 줄의 queue.pop(0)는 맨 앞 원소를 빼낸 뒤에, 뒤에 있던 원소들을 전부 한 칸씩 앞으로 당겨와야 합니다. 즉, 지금까지 큐에 들어간 원소의 수에 비례하는 시간이 걸립니다. 심지어 지금은 방문 체크를 큐에서 뺀 다음에 하기 때문에 이미 큐에 들어간 정점들도 visit만 안 했다면 다시 큐에 들어갈 수 있어 검사해야 하는 양이 더윽 늘어납니다.
또한 27번째 줄의 not in 연산도 리스트를 전부 탐색하면서 검사해야 하기 때문에 visited 배열의 원소 수에 비례하는 시간이 걸립니다. 이런 연산들은 코드를 효율적으로 설계하면 상수 시간에 체크가 가능합니다.
그 외에도 쉽게 간과하기 쉬운 부분들이 있는데 비록 이 코드에서 시간복잡도를 늘리지는 않지만, 내장 함수를 너무 가볍게 보시는 것 같아서 몇 가지 잡아드립니다. list를 set으로 변환하는 과정은 정렬의 일종이기 때문에 O(NlgN) 시간이 걸리며, 45번째 줄은 원소를 전부 하나씩 옮겨넣어야 하기 때문에 O(N) 시간이 걸립니다.
dictionary의 경우에도 접근 시간이 평균 O(1)이기는 하나, 해시를 쓰기 때문에 운이 없으면 수행 시간이 크게 늘어날 수도 있고, 그 자체로도 비교적 무거운 연산일 뿐입니다. 그냥 int형으로 평범하게 배열 접근을 하면 빠르게 될 것을, 굳이 str로 변환하고, 이를 다시 dictionary로 쓰는 과정은 코드를 매우 비효율적으로 만든다고밖에 할 수 없습니다.
내장 함수들을 가볍게 보지 마시고, 그들이 어떤 식으로 구현되어 있는지 잘 알아둔 다음에 실제로 이 기능을 쓰는 것이 시간복잡도를 늘리거나 비효율적으로 만들지 않을지 한 번 생각해 보셨으면 합니다.
jsh05042 6년 전
제목 그대로, 반례 항목 아시는 분이 있나요?
질문 게시판에 올라와있는 항목들 확인해보는데 다 맞게 출력이 되어서 여러 케이스를 만드는데 잘못된 부분을 찾아내기가 쉽지 않네요..