백준 17244 (아맞다우산) - java

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

17244번: 아맞다우산

 

문제

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.

"아 맞다 우산!!!"

경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.

외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.

경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.

경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

 

유형 : BFS + 비트마스킹

 

접근 방식

• '달이 차오른다 가자'라는 문제랑 비슷한 유형의 문제이다.
• 우선 물건의 개수는 최대 5개라는 것을 생각하자.
  • 각 물건에 대해 2의 제곱수를 배정한다. (1 -> 2 -> 4 -> 8 -> 16)
  • 2의 제곱에는 신기한(비트 마스킹의 핵심인) 개념이 있다. 그것은 바로 2의 제곱수로 이루어진 합은 해당 조합으로만 가능하다는 것이다 !!!!!!!!
  • 7을 2의 제곱수의 합으로 만든다면 (1 + 2 + 4) 딱 이 한 경우만 가능하다. (궁금하면 다른 걸로 해봐도 그 조합 1개만 있다)
    • 이  성질을 이용해서 방문 배열을 32정도로 지정하고 구분된 물건을 몇개 먹었는 지 확인한다.
  • 방문 배열을 3차원으로 지정하고 해당 좌표에서 현재 몇개의 물건을 가지고 있는지에 대해 BFS를 수행하면 된다.

현재 좌표의 물건을 가지고 있는지 확인하는 법 !

    // it은 현재 가지고 있는 물건의 총 합 , t는 현재 좌표 물건의 번호
    static boolean already(int it,int t){

        int max = (int)Math.pow(2,count-1); // 구분된 물건의 마지막 번호

        while(max > 0){

            if(max <= it){
                it -= max; // 현재 물건의 값을 총합에서 빼준다.

                if(max == t && it >= 0){
                    return true; // 좌표의 물건을 뺐을 때 값이 0보다 크거나 같다는 건 이미 그 물건을 가지고 있다는 것이다.
                } 
            }

            max /= 2; // 물건은 전부 2의 제곱수이므로 다음 물건 탐색
        }

        return false;
    }

 

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int sx = 0;

    static int sy = 0;

    static int lx = 0;
    static int ly = 0;

    static int count = 0;

    static int[][] board;

    static int[][][] v;

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

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];
        v = new int[n+1][m+1][40];

        for(int i=1;i<=n;i++){

            String line = bf.readLine();

            for(int j=1;j<=m;j++){

                char cur = line.charAt(j-1);

                if(cur == '#'){
                    board[i][j] = -1;
                }else if(cur == 'S'){
                    sx = i;
                    sy = j;
                }else if(cur == 'X'){
                    board[i][j] = (int)Math.pow(2,count);
                    count += 1;
                }else if(cur == 'E'){
                    lx = i;
                    ly = j;
                }

            }
        }


        int full = 0;

        for(int i=0;i<count;i++){
            full += (int)Math.pow(2,i);
        }


        bfs(full);

        bf.close();
    }

    static void print(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static void bfs(int full){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(sx,sy,0));
        v[sx][sy][0] = 1;

        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.c == full && cur.x == lx && cur.y == ly){
                System.out.println(v[lx][ly][full] - 1);
                return;
            }

            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(v[nx][ny][cur.c] == 0 || v[nx][ny][cur.c] > v[cur.x][cur.y][cur.c] + 1){
                        v[nx][ny][cur.c] = v[cur.x][cur.y][cur.c] + 1;
                        q.add(new Node(nx,ny,cur.c));
                    }
                }
                else if(board[nx][ny] >= 1){

                    if(already(cur.c,board[nx][ny])) {
                        if(v[nx][ny][cur.c] == 0 || v[nx][ny][cur.c] > v[cur.x][cur.y][cur.c] + 1){
                            v[nx][ny][cur.c] = v[cur.x][cur.y][cur.c] + 1;
                            q.add(new Node(nx,ny,cur.c));
                        }
                        continue;
                    }

                    int tmp = cur.c + board[nx][ny];

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

    static boolean already(int it,int t){

        int max = (int)Math.pow(2,count-1);

        while(max > 0){

            if(max <= it){
                it -= max;

                if(max == t && it >= 0){
                    return true;
                }
            }

            max /= 2;
        }

        return false;
    }
}
class Node{
    int x;
    int y;

    int c;

    Node(int x,int y,int c){
        this.x = x;
        this.y = y;
        this.c = c;
    }
}