문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

다음과 같은 상황을 분석해 보자.

Greedy로 풀 수 없고, 문제를 풀만한 특별한 규칙을 찾을 수 없다. 따라서, 모든 경우의 수를 조사하는 수밖에 없다.

Algorithm

1. BFS를 통해 물체(오염, 로봇 청소기) 간의 거리를 모두 조사한다.
2. 도달할 수 없는 물체가 있다면 현재 테스트케이스를 종료한다.
3. DFS를 통해, 모든 가능한 순서를 탐색하여 최소를 구한다.
   • 거치지 않은 물체를 선택하여 recursive call을 한다. 이때 bit flags를 이용한다.

Data Structure

• room[]: 방의 상태를 저장, 물체가 있다면 물체의 번호를 지정
• objects[]: 물체 간의 거리를 저장

결과

Other

시간 복잡도는 물체 i에서 시작하는 BFS에 O(WH), 모든 순서를 탐색하는데 O(N!)이다.