문제
이해
격자판에 로봇 청소기가 있습니다. 로봇 청소기는 격자판에 주어진 더러운 칸에 방문하여 모든 곳을 청소해야 합니다. 단, 로봇 청소기는 가구가 있는 곳은 통과하지 못합니다.
격자판에 더러운 곳을 모두 깨끗하게 만들려고 할 때 이동 횟수의 최솟값을 출력하세요.
접근
일단 격자판에서 이동횟수의 최솟값을 구하여야 하기 때문에 BFS를 수행하는 것은 분명합니다. 일반적인 BFS로 얻을 수 있는 것은 출발점에서 각 포인트까지의 최소 이동횟수밖에 없습니다. 하지만, 문제에서는 모든 포인트를 들려야 하는 조건이 있기 때문에 사용하기 쉽지 않아보입니다.
결국 방문순서가 어떻게 되는지에 따라 이동횟수의 값이 달라집니다. 따라서, 각 방문순서를 미리 결정하고 이동횟수를 구한 뒤, 각 경우에서 최솟값을 뽑아내는 방식을 떠올릴 수 있습니다.
이 방법은 시작점을 포함한 각 포인트까지의 거리의 최솟값을 구한 뒤 그래프를 만듭니다. 최단거리로 이루어진 그래프를 활용하여 DFS를 통해 완전탐색을 수행하는 것입니다.
본 문제에서는 격자가 20x20 그리고 포인트가 최대 10개이기 때문에 완전탐색 방식도 가능하지만 사실 이 문제는 TSP 문제와 같습니다.
외판원 순회(TSP) 문제는 완전 탐색도 허용하지만 비트마스킹을 활용한 방문처리로 단순 BFS를 활용할 수 있습니다.
방문배열을 3차원으로 다음과 같이 만듭니다.
visited[방문한 노드(비트마스킹)][row][col]
위와 같이하면 무슨 노드를 방문했는지에 따라 방문처리를 다르게 하기 떄문에 같은 격자라도 중복으로 최단거리를 탐색할 수 있습니다.
위 방식으로 BFS를 수행하면 BFS 기본 특성상 항상 최단거리로 방문합니다. 만일 현재 방문한 위치에서 비트마스킹된 방문 노드들이 모든 포인트를 포함한다면? (이 때의 비트상태는 1111...11 이 되겠습니다.) 그 때의 depth가 최단거리가 됩니다.
풀이
for (int i = 0; i < 4; i++) {
int nx = cur.x + d[0][i];
int ny = cur.y + d[1][i];
if (IsOutBound(nx, ny) || visited[cur.bitState][nx][ny] || board[nx][ny] == WALL) {
continue;
}
xy next = new xy(nx, ny);
next.bitState = cur.bitState;
if (board[nx][ny] == NODE) {
// 몇번째 노드인지 찾기
int idx = -1;
for (int j = 0; j < size; j++) {
xy node = dirtyPoints.get(j);
if (node.x == nx && node.y == ny) {
idx = j;
break;
}
}
next.bitState = cur.bitState | (1 << idx);
if (next.bitState == ((1 << size) - 1)) {
return depth;
}
}
visited[next.bitState][nx][ny] = true;
q.add(next);
}
}위 코드는 bfs의 내부코드입니다. 항상 현재의 방문노드 상태를 가지고 bfs를 수행합니다. 만일 방문한 곳이 포인트라면 비트상태값을 갱신한 뒤 큐에 삽입합니다.
만약, 비트상태가 모두 1인 경우 (모두 방문한 경우)에는 현재까지 측정된 depth값을 리턴하면 됩니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
static final int GND = 0;
static final int WALL = 1;
static final int NODE = 2;
static class xy {
int bitState;
int x;
int y;
public xy(int x, int y) {
this.x = x;
this.y = y;
}
}
static StringTokenizer st = null;
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[][] board;
static xy start;
static List<xy> dirtyPoints;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
if (N == 0 && M == 0) {
break;
}
board = new int[N][M];
dirtyPoints = new ArrayList<>();
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
char c = s.charAt(j);
switch (c) {
case 'x':
board[i][j] = WALL;
break;
case 'o':
start = new xy(i, j);
case '.':
board[i][j] = GND;
break;
case '*':
board[i][j] = NODE;
dirtyPoints.add(new xy(i, j));
default:
break;
}
}
}
sb.append(BFS(start)).append("\n");
}
System.out.println(sb.toString());
}
/**
*
* @param start
* @return 최소값 (단, 모든 곳에 대한 방문 여부가 false라면 -1)
*/
private static int BFS(xy start) {
int size = dirtyPoints.size();
boolean[][][] visited = new boolean[1 << size][N][M];
int depth = 0;
Queue<xy> q = new ArrayDeque<>();
q.add(start);
visited[0][start.x][start.y] = true;
while (q.size() > 0) {
int qsize = q.size();
depth++;
while (qsize-- > 0) {
xy cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + d[0][i];
int ny = cur.y + d[1][i];
if (IsOutBound(nx, ny) || visited[cur.bitState][nx][ny] || board[nx][ny] == WALL) {
continue;
}
xy next = new xy(nx, ny);
next.bitState = cur.bitState;
if (board[nx][ny] == NODE) {
// 몇번째 노드인지 찾기
int idx = -1;
for (int j = 0; j < size; j++) {
xy node = dirtyPoints.get(j);
if (node.x == nx && node.y == ny) {
idx = j;
break;
}
}
next.bitState = cur.bitState | (1 << idx);
if (next.bitState == ((1 << size) - 1)) {
return depth;
}
}
visited[next.bitState][nx][ny] = true;
q.add(next);
}
}
}
return -1;
}
private static boolean IsOutBound(int nx, int ny) {
return nx < 0 || ny < 0 || nx >= N || ny >= M;
}
}결과
