tony9402

4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 로봇 청소기의 시작 위치, 더러운 칸을 정점으로 잡아 새로운 그래프를 만들어 TSP를 해결하면 되는 문제이다. 정점의 개수는 11개(로봇 청소기 위치 + 더러운 칸의 개수)이기 때문에 11!(=39,916,800)가 작아 완전탐색을 돌릴 수 있다. 간선은 A에서 B로 이동할 때 거리를 의미하므로 이 부분은 BFS로 미리 구해놓으면 된다. 아래 코드는 TSP를 계산할 때 완전탐색을 이용하였다. 이를 더 빠르게 돌아가게 하고 싶다면 TSP 관련 알고리즘을 공부하고 적용하면 ..