[백준] 17244번 : 아맞다우산

17244번: 아맞다우산

---

[BFS + 비트마스크]

N x M 격자 맵에서 'X'로 표시된 모든 물건을 챙기고 탈출구 'E'로 최소한의 움직임으로 나가는 방법을 찾는 문제. 격자의 크기 제한이 최대 50x50이고 물건의 개수가 최대 5개라서 비트마스킹을 안써도 메모리적인 부분에서 큰 손실은 없을 것 같으나, 물건이 모두 'X'로 동일하여 현재 내가 특정 정점에 방문했을 때, 어떤 물건을 갖고 있는 지를 체크하는 것이 비트마스킹만큼 좋은 것이 없기에 비트마스킹을 사용했다.

 

먼저 입력을 받을 때 'X'인 곳을 '0', '1', '2', ...처럼 X가 아닌 숫자로 지정해놓는다. 이는 물건에 "인덱스"를 부여하는 효과를 가져오며 물건이 몇 개 존재하는지 또한 알아낼 수 있다.

        int sY = 0, sX = 0;
        char idx = '0';

        for(int i=1; i<=n; i++) {
            char[] str = br.readLine().toCharArray();
            for (int j = 1; j <= m; j++) {
                map[i][j] = str[j - 1];

                if (map[i][j] == 'X') {
                    map[i][j] = idx++;
                    k++;
                } else if (map[i][j] == 'S') {
                    sY = i;
                    sX = j;
                }
            }
        }

그럼 이제 지도에는 S, ., #, E, 0 ~ 4가 존재할 것이고, BFS를 시작점 S에서 부터 탐색을 한다.

 

1) '0', '1', '2', '3', '4' 일 때

 

현재 방문한 정점이 위의 값 중 하나라면, 물건이 있는 곳이다. 이때 내가 이미 해당 물건을 챙겼는지 여부를 비트마스킹으로 체크한다.

만약 이미 챙겼던 물건이라면 item은 변화를 주지 않고 그저 방문한다.

 

아직 챙기지 않은 물건이라면 챙기고 방문한다.

                if(map[ny][nx] >= '0' && map[ny][nx] <= '5'){
                    int num = map[ny][nx] - '0';

                    if( (item & (1 << num)) == 0){
                        nItem = item | (1 << num);

                        visit[ny][nx][nItem] = true;
                        Q.add(new Point(ny, nx, move + 1, nItem));
                        continue;
                    }
                }

2) '#'와 숫자를 제외한 나머지

 

이때는 그냥 방문하기만 하면 된다.

 

# 종료 시퀀스

- 물건을 모두 챙겼는지? 현재 정점이 'E' 인지

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
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, move, item;
        public Point(int yy, int xx, int m, int it){
            y=yy;
            x=xx;
            move=m;
            item=it;
        }
    }

    //n : 높이, m : 너비, k : 물건의 개수
    static int n, m, k;
    static int[] Y = {-1,1,0,0}, X={0,0,-1,1};
    static char[][] map = new char[51][51];
    static boolean[][][] visit = new boolean[51][51][(1 << 6)];

    static int BFS(int sy, int sx) {

        Queue<Point> Q = new LinkedList<>();
        visit[sy][sx][0] = true;

        Q.add(new Point(sy, sx, 0, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int move = p.move;
            int item = p.item;

            if(map[y][x] == 'E' && item == ((1 << k) - 1))
                return move;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];
                int nItem = 0;

                if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx][item] || map[ny][nx] == '#') continue;

                if(map[ny][nx] >= '0' && map[ny][nx] <= '5'){
                    int num = map[ny][nx] - '0';

                    if( (item & (1 << num)) == 0){
                        nItem = item | (1 << num);

                        visit[ny][nx][nItem] = true;
                        Q.add(new Point(ny, nx, move + 1, nItem));
                        continue;
                    }
                }

                visit[ny][nx][item] = true;
                Q.add(new Point(ny, nx, move + 1, item));
            }
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int sY = 0, sX = 0;
        char idx = '0';

        for(int i=1; i<=n; i++) {
            char[] str = br.readLine().toCharArray();
            for (int j = 1; j <= m; j++) {
                map[i][j] = str[j - 1];

                if (map[i][j] == 'X') {
                    map[i][j] = idx++;
                    k++;
                } else if (map[i][j] == 'S') {
                    sY = i;
                    sX = j;
                }
            }
        }
        System.out.println(BFS(sY, sX));
    }
}