백준 4991. 로봇 청소기

https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

우선 딱 보면 bfs 를 이용해야 하는것이 보인다.

그런데 예제의 첫번째 같은 경우만 봐도 직접 세어보면 더러운 곳의 방문 순서도 중요하다는 것을 알 수 있다.

그렇다면 모든 더러운 곳의 순서의 경우의 수를 구해서 시작 지점에서 부터 시작해서 순서대로 방문했을때 거리의 최솟값이 답이다. 

 

그런데 만약 거리를 매번 구한다면, 시간복잡도를 생각해보면

더러운곳의 수 10 이므로 경우의수는 10! = 약 300만,  

한번 bfs 돌릴때 20x20=400, 

더러운 곳의 수 10 이므로 하나의 지점에서 다른 지점까지 계산을 약 열번해야하므로 400 * 10 = 4000 

=> 300만 x 4000 으로 시간초과. 

 

 

시간복잡도를 줄이는 방법은 미리 모든 지점에서 다른 지점까지의 거리를 구해 놓는 것이다. 

어처피 더러운곳과 로봇의 시작지점은 고정되어 있다.

따라서 그 사이의 최단거리를 미리 구하면 시간복잡도 O(약 300만  + 400* (10+9+8+7+6+5+4+3+2+1=55)) 로 끝낼수 있다.