#4991 로봇 청소기

출처:https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

 

문제

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

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

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

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

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

 

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

 

출력

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

 

풀이

bfs + 그래프 구현 + dfs

먼저 로봇 청소기의 시작 위치와 더러운 칸의 위치들을 2차원배열 거리 그래프로 초기화 하여 매 동작마다 불필요한 거리계산을 없앴다. 그래프 구현 과정은 from 에서 to로 가는 거리를 bfs를 통해 구하였고 거리배열 그래프인 v에 v[from][to]=dis, v[to][from]=dis 이렇게 저장하였다.

 

그리고 dfs함수를 통해  최소 거리를 구하였다. 예를들어 총 포인트가 0 1 2 3 이렇게 4개라면 0에서 시작해서

0 1 2 3, 0 1 3 2, 0 2 1 3, 0 2 3 1, 0 3 1 2, 0 3 2 1 이 순서대로 방문하는 경우의 수가 있다. 이때 만약 노드대 노드 방문하는 과정에서 기존 먼저 방문을 완료해서 갱신한 ans값이 현재 진행중인 거리합 보다 작으면 현재 진행하고 있는 노드는 다음 노드로 굳이 방문할 필요가 없어진다. 그래서 코드에 if (ans!=-1&&sum >= ans)return; 이부분이 있고 이런식으로 방문을 하면서 카운트 값이 전체 포인트를 다 방문하게 되면 ans값을 갱신 해주면 된다.

 

코드