인프런 커뮤니티 질문&답변

안녕하세요 923님 ㅎㅎ

뮤탈리스크문제의 시작복잡도는 BFS로 탐색하기니까

O(V+E) = O(60^3 + 6*60^3)=O(150만)

이렇게 계산하는게 맞을까요?

>> 아닙니다. 체력 60이 최대범위라고 해서 60을 기반으로 해서는 안됩니다. 경우의 수를 보시면

int _a[6][3] = {
	{9, 3, 1}, 
	{9, 1, 3}, 
	{3, 1, 9}, 
	{3, 9, 1}, 
	{1, 3, 9}, 
	{1, 9, 3}
};

이렇게 총 6가지인데 이걸 기반으로 산정하셔야 합니다.

최대치로 계산하면

60, 60, 60 이고

9, 3, 1로 하든 뭐든 1로만 공격을 해도 어차피 나머지 3 9는 다른 SCV를 공격하기 때문에 9로 계산해도 무방하게 됩니다. (최소로 공격할 수가 없습니다.)

자 그럼 처음에 7번,

한 SCV 가 죽고.

0, 39, 53이 남죠?

그 다음 9로 다시. 6번.

0, 21, 0이 남죠?

그 다음 9로 다시. 3번.

즉, 최대 16번이 실행되는 문제라는 것을 볼 수 있습니다. 여기서 매번 경우의 수는 6가지이기 때문에

6 ^ 16이라고 보시면 됩니다.

즉,

2,821,109,907,456라는 어머어마한 숫자가 나옵니다. 2조네요.

그렇기 때문에 모든 경우의 수를 따지는 것이 아닌 BFS를 통해서 나름의 가지치기를 통해 문제를 풀어야 합니다.

#####

문제를 풀기 전에

6가지의 선택지를 최대 14번쯤하고 6^14 는 10억보다 크니까 무식하게 풀기는 안되겠다고 생각을 했습니다 ((9+2+1)*14=182 > 60*3)

그런데 강의를 보고 각각 최대 6개의 가지가 있는 60^3의 상태를 탐색하는 문제라고 생각하니까 잘못 생각했다는 걸 알았습니다. 위에처럼 시간복잡도를 계산하는게 맞을까요?

>> 먼저 무식하게 풀까 하고 드가시는 것은 잘하셨습니다. 시간복잡도 계산은 앞에 설명을 드렸구요. 다만, 이 문제 같은 경우 가중치가 같은그래프내에서 횟수의 최소값을 구하는 문제죠? 이 경우는 바로 bfs로 접근해볼까? 하면서 들어가시는 것 또한 좋은 방법입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.