ai4youej   2년 전

첨부한 소스 코드 중, 위의 코드는 맞았습니다!!를 받은 코드이고, 아래의 코드는 시간 초과를 받은 코드입니다.

코드를 분석하니 시간 복잡도의 차이는 동일한 거 같고, 작동 원리도 동일한 것 같은데 왜 위의 코드는 Python 3으로 제출해서 84ms, 아래 코드는 시간 초과라는 극명한 차이가 나는지 궁금합니다.

참고로 예제는 전부 통과합니다!

bamgoesn   2년 전

각 코드에서 bfs 함수가 호출되는 횟수가 다릅니다.

위쪽 코드는 한 지점에서 사방을 탐색할 때, 각 지점을 0으로 그때그때 표시함으로써 이미 탐색하겠다고 visit 리스트에 집어넣은 값을 다시 visit에 집어넣지 않습니다. 즉, visit 리스트에 같은 지점이 두 번 이상 들어가는 일이 없습니다.

반면 아래쪽 코드는, 이 지점을 나중에 탐색하겠다고 찜해놓을 때 그 자리를 0으로 표시하지 않아서, 같은 지점에 대해 그 지점을 탐색하겠다고 visit 배열에 append하는 행위가 중복되어 발생합니다. 이 현상이 발생할 경우 잘못하면 지수적 시간복잡도를 갖게 되기 때문에 시간 초과가 발생합니다.

즉 아래쪽 코드는 visit 배열에 이미 있는 지점을 또 집어넣어서 반복 호출을 하기 때문에 시간 초과가 발생한다고 보시면 되겠습니다. 한번 배추로 가득 찬 입력을 하나 넣어서 visit 리스트가 어떻게 변해가는지 직접 확인해보세요. 디버거를 쓰든 print를 하든...

추가로 visit.pop(0)은 visit의 길이 N에 대해 O(N)입니다. visit을 큐로 사용하기 위해 맨 밑에서 원소를 pop하신 것 같은데, 리스트를 큐로 사용하면 pop 연산과 push 연산 중 하나가 O(N)이 되기 때문에 적절하지 않습니다. collections.deque를 쓰셔야 합니다. 이 문제에선 위쪽 코드 기준으로 visit 배열이 많이 안 길어지기 때문에 이러나 저러나 시간 차이가 딱히 없습니다만, 제한이 더 빡빡한 문제는 이게 실제로 문제가 될 수 있습니다.

한편 visit.pop()은 O(1)입니다. 따라서 visit.pop()을 사용하면 더 좋습니다. 대신 이러면 visit 리스트는 큐가 아닌 스택 역할을 할 것이므로 bfs가 아니라 dfs가 될 겁니다.

---------

위에 설명한 모든 내용은 https://www.acmicpc.net/blog/v...에 있습니다. 중복 방문은 알고리즘 문단에, pop은 Python과 Pypy 문단에 있습니다. 이쪽도 참고해주세요.

ai4youej   2년 전

그렇군요 자주 틀리는 요인을 모두 정독했음에도 아직 BFS에 익숙하지 않아서 더 연습이 필요하네요...!

답변 너무나도 감사합니다

댓글을 작성하려면 로그인해야 합니다.