3-K DFS

작성한 질문수 60

0

비효율적인 부분들이 쌓여있기 때문에 최대한 그런 것들 배제하고 코드를 짜야한다! 어떤 말씀인지 알았습니다! 그런데 예시를 들어주신 코드의 하단 부분에

이렇게 water를 새롭게 초기화를 해주고 있는데 이 코드로는 별 의미가 없는 건가요?? 나름 최적화 해보려고 처음부터가 아닌 새롭게 얼음에서 물이 된 애들만 녹는 것을 시도 했는데 이 방법이 아니였나욥

0

안녕하세요 자르트님 ㅎㅎ

	dfs(y, x);
	while (true) {
		// 하루 지남
		ret++;
		// 얼음 녹이기
		for (pair<int, int> pos : water) {
			removeIce(pos.first, pos.second);
		}

이 코드를 보면 계속해서 시작 지점부터 얼음을 녹이는 것을 볼 수 있습니다.

그러면 어떤 부분이 비효율적일까요?

결국에는 이렇게 되지 않을까요? 예시를 든 그림에서 dfs는 얼음을 녹이기 위해 10번정도의 탐색을 하게 되는 것이죠.

이런 부분들의 비효율이 쌓여서 시간초과가 나는 거 같습니다.

하지만 큐 2개를 활용한 bfs에서는 저렇게 단 4번만에 얼음을 지우는 등의 활동을 할 수가 있는 것이죠.

다만, 이 문제같은 경우 시간초과가 정말 엄청 빡센 문제 중의 하나입니다.

그래서 최대한 효율적으로 짜야 하는 것도 있긴해서.. 좀 맞춰주셔야 하는 것도 있어요 ㅎㅎ

감사합니다.