[ 알고리즘 ] 코딩 - 백준 4991 - 로봇청소기.java

---

문제 링크

www.acmicpc.net/problem/4991

4991번: 로봇 청소기

---

문제 개요

BOJ 4991-(자바) 로봇청소기 - 시뮬레이션 / 구현 / DFS / BFS

방은 크기가 1 ×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1 ×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1 ×1이다. 로봇 청소기는 가구가 놓인 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

---

로직

일반적인 BFS가 아니어서 정말 놀랍도록 어려웠다!!!! 처음 구현할때는 가장 가까운 먼지만 골라서 그리디 하게 구현하면 되지 않을까? 해서 최단거리만을 움직였다가 실패했고, 순열을 이용해서 모든 먼지를 순번을 세워서 고른 다음 BFS를 구현했다가 실패했다.

결론은 BFS로 거리를 먼저 구하고 DFS로 탐색이다!

BFS로 청소기 - 먼지 / 먼지 - 먼지 들의 모든 거리를 구한 다음에 순열을 이용해서 모든 순서를 구하며 최소거리를 찾으면 된다. 세상에!

Step 00. 청소기의 위치와 먼지의 위치를 저장할 배열을 하나 선언한다. 먼지는 최대 10개 있으므로 길이 11로 준다. 입력을 받으면서 청소기는 배열의 0번 인덱스에, 먼지들은 1번부터 차례대로 넣어주자!

Step 01. 청소기와 먼지, 먼지와 먼지들 간에 모든 거리를 BFS로 구해서 2차원 배열에 저장해주자! 이때 BFS는 거리별로 순회하며 가장 먼저 먼지를 만나면 이동 횟수를 return 한다! 이때 도달할 수 없는 경우를 적절히 처리해주자!

Step 02. Step 01의 2차원 배열을 순열로 모두 순회하며 가장 짧은 거리를 구하자! 

Step 03. 모든 입력이 끝날때까지 Step01 ~ Step 02를 반복하자.

 

정말 정말 이해하기 어려웠다.. 많이 노력해야겠다. 

해당 위치에서 갈 수 있는 모든 거리를 측정하는 것을 Flood Fill이라 한다고 한다. 이 방법을 적절히 이용해서 거리 정보만을 이용할 수 있는지를 묻는 문제였던 것 같다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static class Point { // 위치 정보 클래스
		int y, x;

		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	private static int minMove;
	private static int[][] distance;
	private static Point[] list;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			StringTokenizer stt = new StringTokenizer(br.readLine());

			int W = Integer.parseInt(stt.nextToken());
			int H = Integer.parseInt(stt.nextToken());

			if (W == 0 && H == 0)
				break; // 종료

			char[][] map = new char[H][W];
			list = new Point[11]; // 먼지의 갯수 최대 10개. +1인 로봇청소기
			int dust_cnt = 1;
			for (int i = 0; i < H; i++) {
				char[] input = br.readLine().toCharArray();
				for (int j = 0; j < W; j++) {
					map[i][j] = input[j];
					if (input[j] == 'o') { // 0번은 무조건 로봇청소기
						list[0] = new Point(i, j);
					} else if (input[j] == '*') { // 그 뒤는 먼지
						list[dust_cnt++] = new Point(i, j);
					}
				}
			} // input end
			process(map, W, H, dust_cnt);
			System.out.println(minMove);
		} // while end
	}

	private static void process(char[][] map, int w, int h, int dust_cnt) {
		minMove = Integer.MAX_VALUE;
		// 모든 거리를 저장할 2차원 배열
		distance = new int[dust_cnt + 1][dust_cnt + 1];
		// 청소기와 먼지, 먼지와 먼지의 모든 거리를 구해서 저장
		for (int i = 0; i < dust_cnt; i++) { // 먼지의 수만큼 반복
			for (int j = i + 1; j < dust_cnt; j++) {
				int res = bfs(map, w, h, list[i], list[j]);
				if (res == -1) { // 도달할 수 없는 먼지가 있는 경우 더이상 반복 x
					minMove = -1;
					return;
				} else { // 반대에서 오는 경우도 잘 저장해주자
					distance[i][j] = distance[j][i] = res;
				}
			}
		}

		boolean[] selected = new boolean[dust_cnt];

		// 순열을 통해 모든 거리를 순회하자
		permutation(0, 0, 0, dust_cnt, selected);
	}

	private static void permutation(int idx, int cnt, int sum, int dust_cnt, boolean[] selected) {
		if (cnt == dust_cnt - 1) { // 모든 곳 방문
			minMove = minMove < sum ? minMove : sum;
			return;
		}
		for (int i = 1; i < dust_cnt; i++) {
			if (selected[i])
				continue;
			selected[i] = true;
			permutation(i, cnt + 1, sum + distance[idx][i], dust_cnt, selected);
			selected[i] = false;
		}
	}

	private static int bfs(char[][] map, int w, int h, Point src, Point dest) {
		int[] dy = { -1, 1, 0, 0 };
		int[] dx = { 0, 0, -1, 1 };
		boolean[][] visited = new boolean[h][w];
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(src);
		visited[src.y][src.x] = true;
		map[src.y][src.x] = '.';

		int move = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int s = 0; s < size; s++) { // 거리별 탐색
				Point current = queue.poll();
				int y = current.y;
				int x = current.x;

				if (y == dest.y && x == dest.x) { // 목적지 도달
					return move;
				}

				for (int d = 0; d < 4; d++) {
					int next_y = y + dy[d];
					int next_x = x + dx[d];
					if (outRange(next_y, next_x, w, h) || 
						visited[next_y][next_x] || 
						map[next_y][next_x] == 'x')
						continue;
					queue.offer(new Point(next_y, next_x));
					visited[next_y][next_x] = true;
				}
			}
			move++;
		}
		
		// 도달 불가
		return -1;
	}

	private static boolean outRange(int next_y, int next_x, int w, int h) {
		return next_y < 0 || next_y >= h || next_x < 0 || next_x >= w;
	}
}