예제는 크기가 커봐야 4*10이니까 당연히 빠릅니다. 제가 보기에 이 코드는 시간복잡도가 O(N^2 * M^2)인데, 500*500을 넣어보셨나요? 4*10짜리보다는 시간이 3906250000배 정도 더 걸립니다.
지금 코드는 dfs를 이름은 dfs라고 지어놨지만 그냥 아직 방문하지 않은 칸을 하나 찾아서 탐색할 뿐 연결된 정점을 방문하는 것이 아니기 때문에, 그리고 평균 O(NM) 칸을 탐색하는 것을 O(NM)칸 모두에 대해 수행해야 하기 때문에 매우 큰 복잡도가 됩니다.
lswoo3021 5년 전
안녕하세요... 우선 테스트케이스는 다맞고, 체감상 속도가 빠르고 중복되는 것도 없어 보이는데
0%에서 바로 시간초과가 뜨네요.
초기 테스트부터 무한루프에 빠지는 경우가 있는 것 같은데 잘 못찾겠습니다 ㅠㅡㅠ
능력자분들의 조언 부탁드립니다 !!