4991. 로봇 청소기 (골드1)
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 11843 | 4078 | 2689 | 31.830% |
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸
*: 더러운 칸
x: 가구
o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
예제 입력 1
7 5
.......
.o....
.......
.....
.......
15 13
.......x.......
...o...x......
.......x.......
.......x.......
.......x.......
...............
xxxxx.....xxxxx
...............
.......x.......
.......x.......
.......x.......
......x......
.......x.......
10 10
..........
..o.......
..........
..........
..........
.....xxxxx
.....x....
.....x.*..
.....x....
.....x....
0 0
예제 출력 1
8
49
-1
풀이
1. 입력받을 때, 먼지리스트의 인덱스 0에는 청소기, 뒤에는 먼지 위치 넣기 => 청소기와 먼지 간의 거리 파악
2. BFS를 이용해 청소기, 먼지 들 간의 최소거리를 파악하는 배열을 만든다
3. DFS를 이용해 모든 먼지 칸을 방문해서 청소하는 최적의 거리를 파악한다.
public class Search_4991 {
public static int N, M;
// 북,남,서,동
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static int dust_cnt; // 먼지의 갯수 파악
public static String[][] arr; // 위치배열
public static int[][] dust_dis; // 먼지 간의 거리 파악하기 위한 배열
public static Point[] dust_list; // 먼지정보를 담기위한 리스트
public static boolean[] selected; // 리스트에 담긴 먼지들을 방문했는지 확인 배열 - DFS에서 사용
public static int minMove;
static class Point { // 위치 정보 클래스
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) { // 여러번 반복해서 입력을 받는다
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken()); //세로
N = Integer.parseInt(st.nextToken()); //가로
if (N == 0 && M == 0) break; // 입력받기 종료
arr = new String[N][M]; // 전체 위치 배열
dust_list = new Point[11]; // 청소기 + 먼지 갯수 최대 10개
dust_cnt=1; // 0에는 청소기 위치가 들어간다. 인덱스 1부터 먼지 받기
for (int i = 0; i < N; i++) {
String str = br.readLine();
String[] strArr = str.split("");
for (int j = 0; j < M; j++) {
arr[i][j] = strArr[j];
if (arr[i][j].equals("o")) { // 0번은 무조건 로봇청소기
dust_list[0] = new Point(i, j);
} else if (arr[i][j].equals("*")) { // 그 뒤는 먼지
dust_list[dust_cnt++] = new Point(i, j);
}
}
}
minMove = Integer.MAX_VALUE;
process();
System.out.println(minMove);
}
}
public static void process() {
dust_dis = new int[dust_cnt][dust_cnt]; // 먼지 간의 거리 계산 배열
for (int i = 0; i < dust_cnt; i++) { // 먼지의 수만큼 반복
for (int j = i + 1; j < dust_cnt; j++) {
int res = BFS(dust_list[i], dust_list[j]); // 서로의 먼지끼리 거리가 얼마나 되는지 계산
if (res == -1) { // 도달할 수 없는 먼지가 있는 경우 더이상 반복 x
minMove = -1;
return;
} else { // 반대에서 오는 경우도 잘 저장해주자
dust_dis[i][j] = dust_dis[j][i] = res;
}
}
}
// DFS에서 모든 먼지를 거쳐 최소거리를 찾는 방법을 구함
selected = new boolean[dust_cnt];
DFS(0, 0, 0);
}
// 먼지 간의 서로 거리 계산하기
public static int BFS(Point start, Point end) {
int[][] visited = new int[N][M]; //먼지 방문 배열
Queue<Point> que = new LinkedList<Point>();
que.offer(start);
visited[start.x][start.y] = 1; // 시작점 체크
int move = 0;
while (!que.isEmpty()) {
int size = que.size();
for (int s = 0; s < size; s++) { // 거리별 탐색
Point now = que.poll();
int x = now.x;
int y = now.y;
if ( x == end.x && y == end.y) {
return move; // 다른 먼지에 도착했을 때 몇번 움직였는지 리턴
}
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
// 방문했거나 벽이면 넘어가기
if(visited[nx][ny]==1 || arr[nx][ny].equals("x")) continue;
que.offer(new Point(nx, ny));
visited[nx][ny] = 1; // 방문체크
}
}
move++;
}
// 도달 불가
return -1;
}
// 모든 먼지를 방문해 청소하는 최고 거리를 찾는다.
public static void DFS(int idx, int cnt, int sum) {
if (cnt == dust_cnt-1) { // 모든 곳 방문
minMove = Math.min(minMove, sum); // 최솟거리 계산
return;
}
for (int i = 1; i < dust_cnt; i++) {
if (selected[i]) continue;
selected[i] = true;
DFS(i, cnt + 1, sum + dust_dis[idx][i]);
selected[i] = false;
}
}
}
* BFS(먼지들 간 거리 계산), DFS(거리배열에서 최소값 찾기) 혼합 사용
