BOJ 4991 - 로봇 청소기

문제

---

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

---

방문한 곳을 다시 방문할 수 있다는 조건으로 인해 단순한 BFS 방법으로는 해결할 수 없다.

 

1. vector<pair<int, int>> v 에 시작점과 더러운 칸의 좌표를 모두 기록한다.

2. 이중 for문을 이용해 v의 모든 좌표 사이의 거리를 계산하여 기록한다.

3. v[0](시작 점)을 제외한 모든 더러운 칸의 순열 중 최솟값을 계산한다.