[BOJ] 4991 로봇 청소기(Java)
문제
https://www.acmicpc.net/problem/4991
4991번: 로봇 청소기
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
www.acmicpc.net
풀이
- 방의 정보를 입력받아 가구는 -1, 먼지는 1부터 증가하면서 번호를 매겨 높이(height)X너비(width) 크기의 이차원 int 배열 room에 저장한다.
- 비트마스킹을 활용해 방문체크를 하기 위한 (1 << 먼지의 수)X높이X너비 크기의 삼차원 boolean 배열 isVisited를 선언해준다.
- 먼지에 매긴 번호를 이용해 1을 shift하여 현재까지 청소된 먼지의 경우를 체크했는지 확인
- 로봇 청소기의 위치 정보를 담고 있는 Queue 'ROBOT_CLEANER'에 요소가 존재하는 동안 아래 과정을 반복한다.
- 현재 위치에서 사방 탐색을 진행
- 다음 이동할 위치(dx, dy)가 방(범위) 안에 있고, 가구가 아닌 경우 로봇 청소기가 아래 조건에 따라 이동한다.
- 깨끗한 칸이면, 현재까지 청소한 먼지의 경우에서 다음 위치를 방문하지 않은 경우 즉, !isVisited[현재까지 청소한 먼지][dx][dy]인 경우 true로 초기화하고, ROBOT_CLEANER에 (dx, dy, 현재까지 청소한 먼지 정보, 이동횟수 + 1)를 삽입한다.
- 깨끗한 칸이 아니면(먼지이면), 현재까지 청소한 먼지 정보가 담긴 cleandDirties와 현재 위치의 먼지를 bit로 바꿔((1 << (room[dx][dy] - 1)) OR연산(|)으로 현재 위치의 먼지를 청소한 후 먼지 정보 afterCleaning을 저장한다.
현재 칸의 먼지까지 청소한 경우 즉, !isVisited[afterCleaning][dx][dy]인 경우 true로 초기화하고, ROBOT_CLEANER에 (dx, dy, afterCleaning, 이동횟수 + 1)를 삽입한다.
- 모든 먼지를 청소한 경우((1 << 먼지의 수) - 1) 현재까지 이동 횟수를 반환한다.
ex) 먼지가 3개인 경우, 모든 먼지를 청소한 경우 = (1 << 3) - 1 = 7 = 111(bit)
- 로봇 청소기가 모든 먼지를 청소하지 못하고 종료된 경우 -1을 반환한다.
- 위 과정들을 반복하며 결과를 출력하고, width와 height가 0인 경우 반복을 종료한다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static final int[][] DELTAS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private static final Queue<int[]> ROBOT_CLEANER = new ArrayDeque<>();
private static final char DIRTY = '*';
private static final char START = 'o';
private static final char INPUT_FURNITURE = 'x';
private static final int CLEAN = 0;
private static final int FURNITURE = -1;
private static final int X = 0;
private static final int Y = 1;
private static final int CLEANED_DIRTY = 2;
private static final int MOVE = 3;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder answer = new StringBuilder();
while (true) {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int width = Integer.parseInt(stringTokenizer.nextToken());
int height = Integer.parseInt(stringTokenizer.nextToken());
if (width + height == 0) {
break;
}
ROBOT_CLEANER.clear();
int dirtySpace = 0;
int[][] room = new int[height][width];
for (int i = 0; i < height; i++) {
String line = bufferedReader.readLine();
for (int j = 0; j < width; j++) {
char input = line.charAt(j);
if (input == DIRTY) {
room[i][j] = ++dirtySpace;
} else if (input == INPUT_FURNITURE) {
room[i][j] = FURNITURE;
} else if (input == START) {
ROBOT_CLEANER.offer(new int[]{i, j, 0, 0});
}
}
}
answer.append(getMinMove(width, height, (1 << dirtySpace) - 1, room, new boolean[1 << dirtySpace][height][width])).append("\n");
}
System.out.println(answer);
}
private static int getMinMove(int width, int height, int done, int[][] room, boolean[][][] isVisited) {
while (!ROBOT_CLEANER.isEmpty()) {
int[] current = ROBOT_CLEANER.poll();
int x = current[X];
int y = current[Y];
int cleanedDirties = current[CLEANED_DIRTY];
int move = current[MOVE];
if (cleanedDirties == done) {
return move;
}
for (int[] delta : DELTAS) {
int dx = x + delta[X];
int dy = y + delta[Y];
if (dx >= 0 && dx < height && dy >= 0 && dy < width && room[dx][dy] != FURNITURE) {
if (room[dx][dy] == CLEAN) {
if (!isVisited[cleanedDirties][dx][dy]) {
isVisited[cleanedDirties][dx][dy] = true;
ROBOT_CLEANER.offer(new int[]{dx, dy, cleanedDirties, move + 1});
}
} else {
int afterCleaning = cleanedDirties | (1 << (room[dx][dy] - 1));
if (!isVisited[afterCleaning][dx][dy]) {
isVisited[afterCleaning][dx][dy] = true;
ROBOT_CLEANER.offer(new int[]{dx, dy, afterCleaning, move + 1});
}
}
}
}
}
return -1;
}
}