백준 4991번: 로봇 청소기

문제 설명

• https://www.acmicpc.net/problem/4991
• o에서 시작해 모든 *를 수집하는 최단거리를 구하는 문제입니다.

접근법

• 비트마스킹을 활용한 BFS로 풀 수 있습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N,M;
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,-1,0,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			if(N == 0 && M == 0) break;
			
			char[][] board = new char[N][M];

			int[] start = new int[2];
			int dustCnt = 0;
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < M; j++) {
					char c = s.charAt(j);
					board[i][j] = c;
					if(c == 'o') {
						start = new int[] {i,j,0};
						board[i][j] = '.';
					}else if(c == '*') {
						board[i][j] = Integer.toString(dustCnt++).charAt(0); // ++dustCnt하면 안되고 dustCnt++ 해야함 // 1부터 카운팅하면 안되고 0부터 카운팅 해야함
					}
				}
			}			
			
			System.out.println(BFS(start,board,dustCnt));
			
		}
	}
	
	public static int BFS(int[] start,char[][] board, int dustCnt) {
		Queue<int[]> q = new LinkedList<int[]>();
		boolean[][][] v = new boolean[N][M][(int)Math.pow(2, dustCnt)];
		v[start[0]][start[1]][start[2]] = true;
		q.add(start);
		int time = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			while(--size>=0) {
				int[] now = q.poll();
				if(now[2] == ((int)Math.pow(2, dustCnt)-1)) {
					return time;
				}
				for (int d = 0; d < 4; d++) {
					int nx = now[0]+dx[d];
					int ny = now[1]+dy[d];
					if(0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] != 'x' && !v[nx][ny][now[2]]) {
						v[nx][ny][now[2]] = true;
						if(board[nx][ny] == '.') {
							q.add(new int[] {nx,ny,now[2]});
						}else {
							if((now[2] & (1<<(board[nx][ny] -'0'))) == 1) { // 이미 먼지를 치운 곳이면
								q.add(new int[] {nx,ny,now[2]});
							}else { // 아직 먼지를 치우지 않았으면
								int keySet = (now[2] | (1<<(board[nx][ny] -'0')));
								q.add(new int[] {nx,ny,keySet});
							}
						}
					}
				}
			}
			time++;
		}
		return -1;
	}
	
}

기타

같이 풀어보면 좋은 문제

• 백준 17244번: 아맞다우산 // 정답풀이
• 백준 1600번: 말이 되고픈 원숭이 // 정답풀이
• 백준 1194번: 달이 차오른다, 가자. // 정답풀이