문제 링크
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
- .: 깨끗한 칸
- *: 더러운 칸
- x: 가구
- o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
알고리즘: BFS, 브루트포스
풀이
처음 풀 때 입력 부분을 제대로 보지 않고 현재 위치에서 가장 가까운 더러운 칸에 먼저 방문하면 맞지 않을까? 생각하고 직감적으로 풀었다. 당연히 결과는 fail
다시 문제를 자세히 보니 더러운 칸의 개수는 10개를 넘지 않는다고 한다. 그러면 더러운 칸을 방문하는 경우의 수는 10!(약 300만)이다. 10!의 모든 경우의 수를 BFS 돌리면 당연히 비효율적이고 시간제한을 지킬 수 없다. 그래서 각 정점(더러운 칸, 로봇 청소기의 시작 위치)에서 다른 정점으로 BFS를 이용해 이동 거리를 미리 구해놓으면 나머지는 덧셈 연산만으로 이동 거리를 구할 수 있다. 마지막으로 10!의 경우의 수중 가장 작은 이동 거리를 출력하면 끝이다.
소스 코드
import java.io.*;
import java.util.*;
class Node {
int x,y,c;
Node(int x, int y, int c) {
this.x = x;
this.y = y;
this.c = c;
}
}
public class Main {
static final int dx[] = {-1, 0, 1, 0};
static final int dy[] = {0, -1, 0, 1};
static int w,h;
static char room[][];
static boolean visited[][];
static int move[][];
static Node start;
static ArrayList<Node> list;
static boolean is_posi;
static int move_min;
static ArrayList<Integer> result = new ArrayList<>();
static boolean d_visited[];
static StringBuilder sb = new StringBuilder();
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
if(w==0 && h==0) break;
room = new char[h][w];
list = new ArrayList<>();
is_posi = true;
move_min = Integer.MAX_VALUE;
for(int i=0; i<h; i++) {
String input = br.readLine();
for(int j=0; j<w; j++) {
room[i][j] = input.charAt(j);
if(room[i][j]=='o') start = new Node(j,i,0);
else if(room[i][j]=='*') list.add(new Node(j,i,0));
}
}
list.add(0, start);
move = new int[list.size()][list.size()];
d_visited = new boolean[list.size()];
for(int i=0; i<list.size(); i++) {
for(int j=i+1; j<list.size(); j++) {
visited = new boolean[h][w];
if(!BFS(list.get(i), list.get(j), i, j)) {
//방문할 수 없는 더러운 칸이 존재
is_posi = false;
break;
}
}
if(!is_posi) break;
}
if(is_posi) {
DFS();
sb.append(move_min + "\n");
} else {
sb.append(-1 + "\n");
}
}
System.out.println(sb.toString().trim());
}
static boolean BFS(Node s, Node e, int si, int ei) {
Queue<Node> que = new LinkedList<>();
que.add(s);
visited[s.y][s.x] = true;
while(que.size()!=0) {
Node n = que.poll();
if((n.x == e.x) && (n.y == e.y)) {
move[si][ei] = n.c;
move[ei][si] = n.c;
return true;
}
for(int i=0; i<4; i++) {
int nx = n.x + dx[i];
int ny = n.y + dy[i];
if((nx>=0 && nx<=w-1) && (ny>=0 && ny<=h-1)) {
if(!visited[ny][nx] && room[ny][nx] != 'x') {
que.add(new Node(nx, ny, n.c+1));
visited[ny][nx] = true;
}
}
}
}
return false;
}
static void DFS() {
if(result.size()==list.size()-1) {
int mc = move[0][result.get(0)];
for(int i=0; i<result.size()-1; i++) {
mc+= move[result.get(i)][result.get(i+1)];
}
move_min = Math.min(move_min, mc);
return;
}
for(int i=1; i<=list.size()-1; i++) {
if(!d_visited[i]) {
result.add(i);
d_visited[i] = true;
DFS();
result.remove(result.size()-1);
d_visited[i] = false;
}
}
}
}