lswoo3021   2년 전

안녕하세요... 우선 테스트케이스는 다맞고, 체감상 속도가 빠르고 중복되는 것도 없어 보이는데

0%에서 바로 시간초과가 뜨네요. 

초기 테스트부터 무한루프에 빠지는 경우가 있는 것 같은데 잘 못찾겠습니다 ㅠㅡㅠ 

능력자분들의 조언 부탁드립니다 !! 

djm03178   2년 전

예제는 크기가 커봐야 4*10이니까 당연히 빠릅니다. 제가 보기에 이 코드는 시간복잡도가 O(N^2 * M^2)인데, 500*500을 넣어보셨나요? 4*10짜리보다는 시간이 3906250000배 정도 더 걸립니다.

지금 코드는 dfs를 이름은 dfs라고 지어놨지만 그냥 아직 방문하지 않은 칸을 하나 찾아서 탐색할 뿐 연결된 정점을 방문하는 것이 아니기 때문에, 그리고 평균 O(NM) 칸을 탐색하는 것을 O(NM)칸 모두에 대해 수행해야 하기 때문에 매우 큰 복잡도가 됩니다.

lswoo3021   2년 전

@djm03178 감사합니다 ㅠㅡㅠ.. input으로 반복문돌려서 해봤더니 30*30 정도까지만 되고 그 이후로는 스택오버플로 나네요 ... 시간이 부족하다고 생각해서 그냥 직관적으로 생각나는대로 그대로 구현했는데 중복되는 경우도 존재하고 좋은방법이 아니었네요. 다른분들 풀이를 검색해보니 ㅏ 도형을 제외하고는 인접방문을 하는 dfs로 해결했더라구요. 동일경우에 대해서 중복이 없이 할수있겠다 싶었어요. 저는 ㅠㅡㅠ 테트로미노 보고서 왜 그런생각을 하지 못할까요 ㅠㅡㅠ 다들 대단하신것 같아요 ... 혹시 제가 풀이했덪 무식한 방법으로 개선해서 시간복잡도를 개선할 수는 없겠죠 ?! 혹시 다른 분들의 풀이법인 dfs외에 다른 방법도 있을까요 ?! 감사합니다! 

djm03178   2년 전

지금 코드에서 조금만 수정해도 됩니다. dfs에서 다음 방문할 곳을 찾지 말고, process에서 모든 좌표에 대해서 순차적으로 dfs를 한 번씩 호출해보세요.

lswoo3021   2년 전

@djm03178 하앍 ㅠㅡㅠ 됐습니다 됐어요 !!! 정답처리 됐습니다.. 너무 신경써서 답변해주시고 실시간에 가깝게 피드백 주셔서 감사합니다! 

사실 아직 정확히 시간복잡도를 잘따지지 못하여 ... 어떻게 중복이 고쳐진건지는 다시 공부해봐야겟네요 감사합니다! 

djm03178   2년 전

중복이 문제가 아니라, 64~48번째 줄의 루프가 문제입니다.

n, m이 모두 500이라고 생각해보세요. 그러면 처음에 process에서는 (0,0)을 보고 들어갑니다.

dfs(0,0)에서는 (0,0)과 (0,1)을 확인하고 dfs(0,1)을 호출한 뒤, (0,2)부터 (n-1,m-1)까지 모두 확인합니다.

dfs(1,1)에서는 (0,0), (0,1), (0,2)를 확인하고 dfs(0,2)를 호출한 뒤, (0,3)부터 (n-1, m-1)까지 모두 확인합니다.

이런 식으로 모든 칸에 대해서 보면 총 n*m칸 모두가 (0,0)칸부터 (n-1,m-1)칸까지 n*m칸 모두에 대해 확인을 해야 함을 알 수 있습니다. 그래서 n*m * n*m = n^2 * m^2이 되는 것입니다.

lswoo3021   2년 전

@djm03178 그렇군요 ㅠㅡㅠ dfs같은경우 모든경우 탐색을 위해 백트래킹을 해주고, 깊이에 제한을 두어 종료조건을 설정하는데,,, 이번 문제에서는 그게 아니라 이중 for문으로 반복만 하면 되는 것을 착각하여 dfs로 작성을 하려했던 것 같습니다... 정말감사해요 ㅠㅡㅠ 덕분에 많이 배워가는 느낌입니다...혼자서는 몇일이 지나야 겨우 깨달을까 말까인데 ㅠㅡㅠ 감사드려요!

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