sort의 위치에 따른 시간초과 이유

Question

안녕하세요 강사님 나무 재테크의 문제에서 sort의 위치에 따라 시간초과가 나서 질문드립니다. 저는 나무가 번식할때마다 sort를 해주었는데요. 나무가 번식할때 8번 sort를 하게된다고 이해했습니다. 시간초과 코드입니다. http://boj.kr/747f87a580cb4baa93829723a74c5e0c 하지만 이렇게 하면 시간초과가 나서 강사님의 코드처럼 나무가 영양분을 먹을때 sort를 하니 통과하였습니다.   나무가 영양분을 먹을때 sort를 하면 나무가 번식하지 않아도 계속 sort를 하게되는데 왜 번식할떄만 sort하는것보다 시간이 적게 걸리는 걸까요??   성공 코드입니다 http://boj.kr/36fb687d7cb644169aa39f251d50051e

큰돌 · Answer

안녕하세요 sol님 ㅎㅎ 단순하게 생각하시면 됩니다. void fall(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int t = 0; t < ground[i][j].size(); t++){ int tree = ground[i][j][t]; if(tree % 5 == 0){ dfs(i,j); } } } } } 자 일단, 이 코드 dfs를 매번 맵을 탐색해나가면서 돌리죠? dfs의 경우 void dfs(int y, int x){ for(int i = 0; i < 8; i++){ int ny = y + dy[i]; int nx = x + dx[i]; if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue; ground[ny][nx].push_back(1); sort(ground[ny][nx].begin(), ground[ny][nx].end()); } } 간단한 8개의 칸을 확인하며 PUSH하는 로직입니다. 그러나 여기서 SORT를 넣게 되면 최대 8의 시간복잡도를 가졌던 DFS는 단숨에 8 * 8log8 정도의 시간복잡도를 가지게 됩니다. 매번 정렬을 하니까요. sort는 nlogn의 시간복잡도를 가집니다. 그래서 시간초과가 뜬 거 같습니다. 불필요하다 또는 비효율적이다. 라고 느끼시는 코드는 지워주는게 좋습니다. 매번 8개의 칸을 확인할 때마다 sort를 굳이 할 필요가 있을까요? 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.