[java] 백준(BOJ) - 로봇청소기

문제

백준-로봇청소기
로봇청소기가 모든 먼지를 제거하는데 필요한 이동횟수의 최솟값을 구하는 문제

• 제한 사항
  방의 가로 크기 w : 1 <= w <= 20
  방의 세로 크기 h : 1 <= h <= 20
  방의 정보 :
  • . : 깨끗한 칸
  • * : 더러운 칸
  • x : 가구(이동 불가)
  • o : 시작 위치
    더러운 칸의 수는 10개를 넘지 않고 로봇청소기의 수는 1개이다

풀이

비트마스킹에 익숙해지기 위해서 로봇청소기 문제를 풀어봤다

• 요약
  • 입력정보를 받을 때 시작위치와 더러운 칸을 처리한다
    • 시작위치의 경우, dusts의 0번째에 저장하고, map에서 ‘A’로 변경한다
    • 더러운 칸의 경우, dusts에 위치정보를 추가하고, map에서 ‘B’부터 차례대로 변경한다
  • steps배열을 생성해서 dusts의 0번째부터(시작위치부터) 그 외 다른 원소들까지의 거리를 저장한다
  • [현재 위치][방문상태]를 저장할 memo 배열을 생성한다
  • tsp(시작 위치의 dusts 인덱스, 방문 상태)를 호출한다(tsp(0,1))

    tsp(curr[현재위치], state[방문상태])
    모든 칸을 다 방문한 경우, 0을 리턴한다
    이미 저장된 값(memo[curr][state])가 있으면 해당 값을 리턴한다
    memo[curr][state] = MAX를 저장하고, dusts의 원소들을 순회한다
    방문하지 않았고, 갈 수 있는(steps에 0보다 큰 값을 가진) 인덱스 i가 있다면,
    tsp(i, state \ 1 << i) + 거리(steps[curr][i])를 이용해서 memo[curr][state]를 최솟값으로 갱신한다
    최종 memo[curr][state]를 리턴한다

더러운 칸의 정보를 LinkedList<Point> dusts에 담았다
dusts의 0번째에는 로봇청소기의 시작위치를 넣고 1번째부터는 더러운 칸의 정보를 담았다
시작위치로부터 각 더러운 칸마다 거리를 미리 구해놓았다
각 위치마다 각각의 거리를 계산하는 것이 불필요하다고 생각했다
또한, dusts의 0번째부터 bfs를 돌려서 각 위치에 A,B,C.. 로 저장했기 때문에 대문자를 만나면 ‘A’-65를 이용해서 steps를 채웠다

tsp(현재위치 : curr, 방문 상태 : state)를 하면서
memo[curr][state]값을 갱신한다
memo의 초기값은 -1로 MAX값이 있으면 경로의 유효하지 않음을 의미한다

시행착오

하.. 문제를 제대로 읽지않는 실수는 ^^ 정말..
입력값이 7 5 일때 map[7][5]라고 했으나 map[5][7] 이었다..
유심히 살펴보지않은 나의 잘못.. ArrayIndexOutof에러를 보고 알았다

소스코드

// 패키지 생략

public class Main {
	private static char[][] map; // 지도 정보
	static int memo[][]; // 메모할 배열
	static int steps[][]; // 거리 저장
	static final int MAX = 987654321; // 최댓값
	static int N, M; // 가로 세로 크기  
	static LinkedList<Point> dusts = new LinkedList<>();
	static Queue<Point> q = new LinkedList<>();

	static int dx[] = { 1, -1, 0, 0 };
	static int dy[] = { 0, 0, 1, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = -1;
		M = -1;
		StringBuilder sb = new StringBuilder();
		while (true) {

			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			if (N == 0 && M == 0) { // 종료 조건
				System.out.println(sb.toString());
				return;
			}
			map = new char[M][N];
			dusts.clear();
			// 입력
			int idx = 1;
			for (int i = 0; i < M; i++) {
				String tmp = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = tmp.charAt(j);
					if (map[i][j] == 'o') { // 시작위치는 0번째에 저장
						dusts.add(0, new Point(i,j));
						map[i][j] = 'A';
					} else if (map[i][j] == '*') {
						dusts.add(new Point(i, j));
						map[i][j] = (char) (idx++ + 65);
					}
				}
			}
			steps = new int[dusts.size()][dusts.size()];
			initSteps(); // 각 거리 미리 계산함
			memo = new int[dusts.size()][1 << dusts.size()];
			for (int i = 0; i < memo.length; i++) {
				Arrays.fill(memo[i], -1);
			}

			int result = tsp(0, 1);
			sb.append(result == MAX ? -1 : result).append("\n");

		}
	}

	private static void initSteps() {
		for (int i = 0; i < dusts.size(); i++) {
			getDists(i);
		}
	}

	private static int tsp(int curr, int state) {
		if ((1 << dusts.size()) - 1 == state) { // 다 방문했으면
			return 0;
		}
		if (memo[curr][state] >= 0) // 저장된 값이 있으면
			return memo[curr][state];

		memo[curr][state] = MAX;
		for (int i = 0; i < dusts.size(); i++) {
			if ((state & (1 << i)) == 0 && steps[curr][i] > 0) {
				memo[curr][state] = Math.min(memo[curr][state], tsp(i, state | (1 << i)) + steps[curr][i]);
			}
		}
		return memo[curr][state];
	}

	private static void getDists(int loc) {
		// dust의 i번째에서 다른 알파벳까지 거리 계산
		q.clear();
		Point start = new Point(dusts.get(loc).x, dusts.get(loc).y);
		q.add(start);
		boolean[][] chk = new boolean[M][N];
		chk[start.x][start.y] = true;
		int cnt = 0;

		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point curr = q.poll();
				if (map[curr.x][curr.y] - 65 >= 0 && map[curr.x][curr.y] - 65 <= 11) { // 더러운 곳이 10개를 넘지 않으므로 + 시작위치 = 11
					steps[loc][map[curr.x][curr.y] - 65] = cnt;
					steps[map[curr.x][curr.y] - 65][loc] = cnt;
				}
				for (int j = 0; j < 4; j++) {
					int nx = curr.x + dx[j];
					int ny = curr.y + dy[j];
					if (nx > -1 && ny > -1 && nx < M && ny < N && map[nx][ny] != 'x' && !chk[nx][ny]) {
						chk[nx][ny] = true;
						q.add(new Point(nx, ny));
					}
				}
			}
			cnt++;
		}
	}

}