백준 4991 (로봇 청소기) - java

https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

고려해야 할 점이 몇 가지 있는 BFS 문제이다.

• 더러운 칸의 개수가 10개 이하이다 -> 각 먼지를 구분하기 위해 비트마스킹을 사용 ?
• 즉 먼지에 대한 구분이 필요하다. 

먼지에 대한 구분 처리를 위해 방문 배열을 3차원으로 생성했다. 최소 거리를 가기 위해 전에 갔던 자리를 다시 갈 수 있기 때문이다. 하지만 다시 가더라도 (먼지 개수) 는 다를 것이다.

 

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

public class Main {

    static int n = 0;
    static int m = 0;
    static int[][] board;

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

    static int[] dust = {1,2,4,8,16,32,64,128,256,512};
    // 먼지 개수는 10개 이하이기 때문에 비트 마스킹보다는 2의 제곱 수 사용

    static int result = Integer.MAX_VALUE;

    static int allDust = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true)
        {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            if(n==0&&m==0)
                break;

            board = new int[n+1][m+1];
            result = Integer.MAX_VALUE;
            int start = 1;
            allDust = 0;
            int sx = 0;
            int sy = 0;
            for(int i=1;i<=n;i++)
            {
                String line = br.readLine();
                for(int j=1;j<=m;j++)
                {
                    if(line.charAt(j-1)=='o')
                    {
                        sx = i;
                        sy = j;
                    }

                    else if(line.charAt(j-1)=='x')
                    {
                        board[i][j] = -1;
                    }

                    else if(line.charAt(j-1)=='*')
                    {
                        board[i][j] = start; // 먼지 구분
                        allDust += start;
                        start = start * 2; 
                    }
                }
            }
            search(sx,sy);

            if(result==Integer.MAX_VALUE)
                result = -1;
            sb.append(result+"\n");
        }
        System.out.print(sb);

        br.close();
    }

    static void search(int sx,int sy)
    {
        Queue<point> q = new LinkedList<>();
        int[][][] visit = new int[n+1][m+1][2000];
        visit[sx][sy][0] = 1;
        q.add(new point(sx,sy,0));

        while(!q.isEmpty())
        {
            point cur = q.poll();
            if(cur.dust==allDust)
            {
                result = Math.min(result , visit[cur.x][cur.y][cur.dust] - 1);
                continue;
            }

            for(int i=0;i<4;i++)
            {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx<1||nx>n||ny<1||ny>m)
                    continue;

                if(board[nx][ny]==-1)
                    continue;

                if(board[nx][ny]==0)
                {
                    if(visit[nx][ny][cur.dust]==0|| visit[nx][ny][cur.dust] > visit[cur.x][cur.y][cur.dust] + 1)
                    {
                        visit[nx][ny][cur.dust] = visit[cur.x][cur.y][cur.dust] + 1;
                        q.add(new point(nx,ny,cur.dust));
                    }
                }

                else if(board[nx][ny]>=1){

                    if(!isIt(board[nx][ny],cur.dust)) {
                        int tmp = cur.dust + board[nx][ny];

                        if (visit[nx][ny][tmp] == 0 || visit[nx][ny][tmp] > visit[cur.x][cur.y][cur.dust] + 1)
                        {
                            visit[nx][ny][tmp] = visit[cur.x][cur.y][cur.dust] + 1;
                            q.add(new point(nx,ny,tmp));
                        }
                    }

                    else{
                        if(visit[nx][ny][cur.dust]==0||visit[nx][ny][cur.dust] > visit[cur.x][cur.y][cur.dust] + 1)
                        {
                            visit[nx][ny][cur.dust] = visit[cur.x][cur.y][cur.dust] + 1;
                            q.add(new point(nx,ny,cur.dust));
                        }
                    }
                }
            }
        }
    }

    static boolean isIt(int nowDust,int cur)
    {
        int idx = 0;
        for(int i=0;i<=9;i++)
        {
            if(dust[i]==nowDust) {
                idx = i;
                break;
            }
        }

        for(int i=9;i>=0;i--)
        {
            if(dust[i] > cur)
                continue;

            if(i==idx&&cur>=dust[i])
            {
                return true;
            }

            else if(cur >= dust[i])
            {
                cur -= dust[i];
            }
        }

        return false;
    }

}
class point
{
    int x;
    int y;

    int dust;

    point(int x,int y,int dust)
    {
        this.x = x;
        this.y = y;
        this.dust = dust;
    }
}