로봇청소기
https://www.acmicpc.net/problem/4991
다시 푼 문제이다. 어떻게 풀어야하는지 전혀 감이 잡히지 않았다. 해설을 보고 이해를 하였다.
풀이
- map 입력을 받으며, 더러운 칸이면 칸의 위치를 백터에 저장한다.
- 시작 위치에서 더러운 칸을 이동하는 최소값을 next_permutation()을 이용하여 구한다.
예시
- 다음과 같이 더러운 칸이 세 곳 이라고 하자.
- Start Point
- Dirty Point 01
- Dirty Point 02
- Dirty Point 03
- 방문하는 순서는 다음과 같은 경우들이 있다. 이 때, next_permutation() 을 이용한다.
- S -> 01 -> 02 -> 03
- S -> 01 -> 03 -> 02
- S -> 02 -> 01 -> 03
- S -> 02 -> 03 -> 01
- S -> 03 -> 01 -> 02
- S -> 03 -> 02 -> 01
- 그렇다면 이동 경로 거리는 어떻게 구할까? 위 예시 중, 가장 위의 경우를 보자.
- S -> 01 최단 거리 : S를 시작점으로 하는 BFS 에서 구할 수 있다.
- 01 -> 02 최단 거리 : 01을 시작점으로 하는 BFS 에서 구할 수 있다.
- 02 -> 03 최단 거리 : 02를 시작점으로 하는 BFS 에서 구할 수 있다.