[BOJ] 보물섬_2589

 

위 문제의 풀이 과정은 너무나 쉽다.

근데 너무 어렵게 생각했다,,,

나는 이 문제를 풀 때, 트리의 지름 문제를 떠올렸다.

해당 지점에서 가장 먼 지점을 선택한 후, 그 지점에서 가장 먼 지점을 구한다면 그것이 최대 길이가 되는 줄 알았다.

근데 결국 정답은 그냥 전체 다 돌면서 BFS하면 해결되는 문제였다...

이렇게 쉬운 문제를 왜 어렵게 돌아서 가려고 한 것 일까?

지금은 이 문제에 대해 생각을 더 해보자.

 

어렵게 생각한 이유가 무엇일까?

전체를 bfs로 도는 방식은 시간초과가 날 것 같은 느낌이 강하게 든다.!

 

뭔가 이러한 느낌이 강해서,,, 말도 안되는 트리의 지름 방법 떠올리고! 뭐 무슨 visited 다시 계속 초기화하고!!

그랬던 것 같다..ㅠㅠ 이번에 알았으니 깊게 잘 생각해보자.

 

이 문제점, 해결해보자!

50 * 50 맵을 이중 for문으로 돌면서 전부 bfs()했을 때의 시간 복잡도는 몇일까?

 

최악의 경우를 생각해보자.

50 * 50 맵이 전부 'L'이라고 가정한다면, 한 지점마다 2500의 연산을 해야한다.

이러한 연산을 최대 2500번 해야 한다.

그렇다면 2500 * 2500이 된다.

6250000(6백25만)의 연산을 수행한다.

1초에 1억의 연산이 걸린다고 했을 때, 훨씬 작은 수이다.

 

이렇게 간단한 계산만으로도 시간 복잡도를 어느 정도는 유추할 수 있다.

다음부터는 전수조사의 방식을 떠올려 보고, 그것이 시간초과가 나올 문제인지를 파악한 후 어디에서 최적화가 필요한지를 생각해보자.

 

조금만 더 힘내보자!!