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

작성한 질문수 17

0

안녕하세요 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점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.