BOJ 4991 로봇 청소기
BOJ 4991 로봇 청소기
https://www.acmicpc.net/problem/4991
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 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을 추가 후 다음 케이스 진행시작점을 시작으로 더러운 칸을 순열로 모두 방문하며 각 칸 사이의 거리를 더함
각 칸을 모두 방문하며 계산된 거리가 최소인 거리를 정답에 추가 후 다음 케이스 진행
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Position {
private Point point;
private int level;
public Position(Point point, int level) {
this.point = point;
this.level = level;
}
}
static int w, h, answer;
static boolean flag;
static char[][] map;
static ArrayList<Point> dirty;
static Point start;
static int[][] dis;
static int[] dirRow = {-1, 0, 1, 0}, dirCol = {0, 1, 0, -1};
static boolean[] selected = new boolean[10];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
StringBuilder answers = new StringBuilder();
while (w != 0 && h != 0) {
dirty = new ArrayList<>();
answer = Integer.MAX_VALUE;
flag = false;
map = new char[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = (char) br.read();
if(map[i][j] == 'o') start = new Point(i, j);
else if (map[i][j] == '*') dirty.add(new Point(i, j));
}
br.readLine();
}
st = new StringTokenizer(br.readLine());
initDistances();
if(flag) {
answers.append(-1).append('\n');
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
continue;
}
for (int i = 0; i < dirty.size(); i++) {
selected[i] = true;
dfs(1, dis[0][i + 1], i);
selected[i] = false;
}
answers.append(answer).append('\n');
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
}
System.out.println(answers);
}
static void dfs(int level, int distance, int last) {
if(level == dirty.size()) {
answer = Integer.min(answer, distance);
return;
}
for (int i = 0; i < dirty.size(); i++) {
if(!selected[i]) {
selected[i] = true;
dfs(level + 1, distance + dis[last + 1][i + 1], i);
selected[i] = false;
}
}
}
static void initDistances() {
dis = new int[dirty.size() + 1][dirty.size() + 1];
for (int i = 0; i < dirty.size(); i++) {
dis[0][i + 1] = calDistance(start, dirty.get(i));
if(dis[0][i + 1] == -1) {
flag = true;
return;
}
dis[i + 1][0] = dis[0][i + 1];
}
for (int i = 0; i < dirty.size(); i++) {
for (int j = i + 1; j < dirty.size(); j++) {
dis[i + 1][j + 1] = calDistance(dirty.get(i), dirty.get(j));
if(dis[i + 1][j + 1] == -1) {
flag = true;
return;
}
dis[j + 1][i + 1] = dis[i + 1][j + 1];
}
}
}
static int calDistance(Point start, Point end) {
Queue<Position> queue = new LinkedList<>();
queue.offer(new Position(start, 0));
map[start.x][start.y] = 'V';
while (!queue.isEmpty()) {
Position check = queue.poll();
for (int i = 0; i < dirRow.length; i++) {
Point newPoint = new Point(check.point.x + dirRow[i], check.point.y + dirCol[i]);
if(newPoint.equals(end)) {
for (int j = 0; j < h; j++) {
for (int k = 0; k < w; k++) {
if(map[j][k] == 'V') map[j][k] = '.';
}
}
return check.level + 1;
}
boolean isInside = newPoint.x >= 0 && newPoint.x < h && newPoint.y >= 0 && newPoint.y < w;
if(isInside && map[newPoint.x][newPoint.y] != 'x' && map[newPoint.x][newPoint.y] != 'V') {
map[newPoint.x][newPoint.y] = 'V';
queue.offer(new Position(newPoint, check.level + 1));
}
}
}
return -1;
}
}
This post is licensed under CC BY 4.0 by the author.