[백준/자바] 4991 로봇 청소기

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

---

설명

해당 문제를 다음 알고리즘 분류를 가진다.

• 그래프 이론
• 그래프 탐색
• 브루트 포스 알고리즘
• 너비 우선 탐색
• 비트 마스킹

ArrayList를 사용해 먼지의 위치를 넣어준다.

이때 0번째는 로봇 청소기의 위치를 넣어준다.

for(int i = 0; i < m; i++){
	char str[] = br.readLine().toCharArray();
	for(int j = 0; j < n; j++) {
		if(str[j] == 'o') { // 로봇청소기 위치 추가
			dust.add(0, new coordinate(i, j));
		}else if(str[j] == '*') { // 더러운 곳 위치 추가
			dust.add(new coordinate(i, j));
		}
					
		if(str[j] == 'x') {
			map[i][j] = 'x';
		}else {
			map[i][j] = '.';
		}
	}
}

 

로봇 청소기와 각각의 더러운 곳 사이의 거리를 구한다.

또 각각 더러운 곳 사이의 거리를 구한다.

이때, 로봇청소기와 더러운 곳 중 도달할 수 없는 곳이 있다면 더 이상의 계산을 하지 않고 결과를 -1 출력해야 한다.

안 그러면 시간 초과가 발생한다.

for(int i = 0; i < dust.size(); i++){
	for(int j = i+1; j < dust.size(); j++) {
		int len = bfs(dust.get(i), dust.get(j));
		graph[i][j] = graph[j][i] = len;
					
		if(i == 0 && len == -1) { // 로봇 청소기가 더러운 곳으로 도착할 수 없는 경우
			result = -1;
			break;
		}
	}
	if(result == -1) {
		break;
	}
}

static int bfs(coordinate start, coordinate end) {
		Queue<coordinate> q = new LinkedList<>();
		q.offer(start);
		int visited[][] = new int[m][n];
		
		for(int i = 0; i < m; i++) {
			Arrays.fill(visited[i], -1);
		}
		
		visited[start.x][start.y] = 0;
		
		while(!q.isEmpty()) {
			coordinate cur = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int x = cur.x + dx[i];
				int y = cur.y + dy[i];
				
				if(x < 0 || m <= x || y < 0 || n <= y) {
					continue;
				}
				
				if(visited[x][y] != -1 || map[x][y] == 'x') {
					continue;
				}
				
				if(x == end.x && y == end.y) {
					return visited[cur.x][cur.y] + 1;
				}
				
				visited[x][y] = visited[cur.x][cur.y] + 1;
				q.offer(new coordinate(x, y));
				
			}
		}
		
		return -1;
}

 

더러운 칸의 개수는 10개를 넘지 않기 때문에 방문할 더러운 곳의 순열을 구할 수 있다.

static void dfs(String output, boolean[] visited, int depth) {
		if(depth == dust.size()-1) {
			searchMinPath(output);
		}
		
		if(result == -1) {
			return;
		}
		
		for(int i = 1; i < dust.size(); i++) {
			if(visited[i] != true) {
				visited[i] = true;
				dfs(output+i+" ", visited, depth+1);
				visited[i]= false;
			}
		}
}

코드