백준 4991. 로봇 청소기

tose33 2023. 1. 30. 14:55

4991번: 로봇 청소기

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

www.acmicpc.net

우선 딱 보면 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)) 로 끝낼수 있다.