4991번 로봇청소기
난이도
골드1
문제 설명
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을 출력한다.
예제 입력
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
예제 출력
8
49
-1
요구사항
- 시작점에서 모든 '*'(더러운 칸)를 한번 씩 방문하는 최소 이동 횟수.
- 도달 불가능한 '*'가 하나라도 존재하면 -1을 출력.
- 입력은 여러 테스트케이스로 이루어져 있으며 w, h가 0, 0이면 종료.
접근 방식
로봇 청소기(o)와 더러운 칸() 사이의 모든 최단거리를 BFS로 탐색해 인접 리스트를 생성한다. 만약, 하나라도 도달할 수 없는 칸이 존재한다면, 해당 테스트케이스는 -1로 출력한다.
생성한 완전 그래프를 바탕으로 시작점에서 모든 더러운 칸()을 방문하는 최단 경로를 탐색한다. 경로 탐색은 순열 기반의 완전탐색을 적용하여 모든 경로의 거리를 구한 후, 그 중에 최단 거리를 출력하도록 접근하였다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Point{
int x;
int y;
int cnt;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public Point(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
class Edge{
int end;
int weight;
public Edge(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
public class Main{
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int h, w;
while (true){
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
if(w==0 && h==0) return;
char[][] room = new char[h][w];
boolean flag = false;
int idx = 1;
Point[] edge = new Point[11];
for(int i=0; i<h; i++){
String line = br.readLine();
for(int j=0; j<w; j++){
room[i][j] = line.charAt(j);
if(room[i][j] == 'o'){
edge[0] = new Point(i, j);
}
else if(room[i][j] == '*'){
edge[idx++] = new Point(i, j);
}
}
}
// 인접리스트 생성
ArrayList<ArrayList<Edge>> al = new ArrayList<>();
for(int i=0; i<idx; i++){
al.add(new ArrayList<>());
}
for(int i=0; i<idx; i++){
for(int j=i+1; j<idx; j++){
int weight = BFS(edge[i], edge[j], h, w, room);
// 도착 못 한다면 중단 후 -1 출력
if(weight == -1) {
flag = true;
break;
}
al.get(i).add(new Edge(j, weight));
al.get(j).add(new Edge(i, weight));
}
}
if(flag){
System.out.println(-1);
continue;
}
int[] ch = new int[idx];
ch[0] = 1;
answer=Integer.MAX_VALUE;
permutation(0, idx, ch, 0, al, 0);
System.out.println(answer);
}
}
// 1->2->3->4 등 순열 구하기
static void permutation(int L, int size, int[] ch, int sum, ArrayList<ArrayList<Edge>> al, int start){
if(L == size-1){
answer = Math.min(answer, sum);
}
else{
for(Edge e : al.get(start)){
if(ch[e.end] == 0){
ch[e.end] = 1;
permutation(L+1, size, ch, sum+e.weight, al, e.end);
ch[e.end] = 0;
}
}
}
}
// 로봇 청소기 및 먼지들의 최단 경로
static int BFS(Point start, Point end, int h, int w, char[][] room){
Queue<Point> q = new LinkedList<>();
int[][] visited = new int[h][w];
q.offer(new Point(start.x, start.y, 0));
visited[start.x][start.y] = 1;
while (!q.isEmpty()){
Point now = q.poll();
if(now.x == end.x && now.y == end.y){
return now.cnt;
}
for(int i=0; i<4; i++){
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
if(visited[nx][ny] == 0 && room[nx][ny] != 'x'){
visited[nx][ny] = 1;
q.offer(new Point(nx, ny, now.cnt+1));
}
}
}
return -1;
}
}느낀점
BFS로 얻은 최단거리를 바탕으로 완전 가중치 그래프를 구성하고 이를 인접리스트로 저장하는 과정을 직접 구현하며 자료구조, 모델링 감각을 되살릴 수 있었다. 인접 리스트의 활용 빈도가 낮아 초반에 매우 낮설게 느껴졌다. 하지만, 이 문제를 통해 인접 리스트를 생성하여 완전 그래프를 작성하는 감각과 순열 기반의 완전 탐색에 대한 코드 구현 감각을 키울 수 있어서 좋은 문제 풀이 시간이였다고 생각한다.
또한, DP(동적프로그래밍)을 통해 이 문제를 해결할 수 있을 것이라고 느꼈고 다음에는 DP를 이용하여 문제를 해결하는 시간을 가져야 될 것이라고 생각했다.
