문제링크

🟣 시간복잡도

결국 비트마스킹으로 풀었다.

1번째 풀이법 : DFS

• DFS로 더러운칸 순열로 뽑아서 계산하기
  전체 노드 : 400개
  더러운칸 최대 개수 : 10개
  더러운칸 순열 갯수 X BFS돌리는 횟수 X 칸 갯수
  10! x O(N+2N) x 10
  (BFS 시간복잡도는 노드갯수 + 간선의 갯수)

=> 시간복잡도가 엄청 크게 나옴

2번째 풀이법 : DFS

• 1번째 방법에서 순열로 뽑을 때마다 BFS돌리는 것이 아니라 미리 더러운칸들, 시작지점 각각의 거리를 구하고 시작

3번째 풀이법 : 비트마스크

🟢 사용한 알고리즘 : 비트마스크

• 알고리즘보다는 테크닉 중 하나로써, 정수의 이진수 표현을 활용한 기법이다.

길이가 5인 집합 { 0, 1, 2, 3, 4 } 가 존재한다고 가정해본다.여기서 몇가지 요소를 뽑아 어떤 요소를 선택했는 지 표현할 수 있다.

즉, 집합의 어떤 요소를 구성하고 있는지를 나타내는 부분집합을 어떻게 표현할 수 있는가?

{ 1, 2, 3, 4 }, { 1, 2, 4 }, { 2, 4 }, { 1 } 

위와 같은 형태로, Integer 형으로 인덱스를 활용할 수 있다면, 단순히 boolean 배열을 통해 구현할 수도 있다.

int[] array1 = [1, 1, 1, 1, 0];
int[] array2 = [1, 1, 0, 1, 0]; 
int[] array3 = [1, 0, 1, 0, 0];

하지만 이건 많은 메모리를 차지하고 오버헤드가 증가한다.

비트마스크를 통해 더욱 효율적이게 할 수 있다.

{ 0, 1, 2, 3, 4 } => 11111 => 31
{ 1, 2, 3, 4 } => 11110 = > 30
{ 1, 2, 4 } => 10110 => 22
{ 2, 4 } => 10100 => 20
{ 1 } => 00010 => 2

부분집합을 배열이 아닌 정수를 통해 나타낼 수 있게 된다.
즉, 20 이란 정수는 부분집합 { 2, 4 } 를 나타내는 것을 의미한다.
{ 2, 4 } 부분집합에서 i를 추가하고 싶으면, 단순히 i번째 비트의 값을 1로 변경해주면 된다.

이러한 삽입, 삭제, 조회와 같은 행위는 비트 연산을 통해 쉽게 제어할 수 있다.

비트연산자

AND 연산(&)

• 대응하는 두 비트가 모두 1일 때, 1을 반환.
• 1010 & 1111 = 1010

OR 연산(|)

• 대응하는 두 비트가 모두 1 또는 하나라도 1일 때, 1을 반환.

• 1010 | 1111 = 1111

시프트(Shift) 연산(>>, <<)

• 왼쪽 또는 오른쪽으로 비트를 옮긴다.
• 00001010 << 2 = 101000
• 00001010 >> 2 = 000010
• 왼쪽 시프트는 A * 2^B 를 의미하고, 오른쪽 시프트는 A / 2^B 를 의미한다.

🟡 문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point {
    int x;
    int y;
    int d;
    int mask;

    public Point(int x, int y, int d, int mask) {
        this.x = x;
        this.y = y;
        this.d = d;
        this.mask = mask;
    }
}

public class Main {
    static int n,m;
    static boolean[][][] visited;
    static int[][] map;
    static Queue<Point> Q;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    public int bfs(int idx) {

        while (!Q.isEmpty()) {
            Point now = Q.poll();
            int x = now.x;
            int y = now.y;
            int mask = now.mask;
            int d = now.d;

            if (mask == (1 << idx) - 1) {
                return d;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nd = d+1;
                int nMask = now.mask;

                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(map[nx][ny] == -1) continue; // 벽이면 갈수 없다.
                if (map[nx][ny] > 0) { //쓰레기가 있는 칸이라면 마스크값 업데이트
                    nMask |= (1 << (map[nx][ny]-1));
                }
                if(visited[nx][ny][nMask]) continue;
                Q.add(new Point(nx, ny, nd, nMask));
                visited[nx][ny][nMask] = true;
            }
        }
        return -1;
    }


    public static void main(String[] args) throws IOException {
        Main T = new Main();
        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());
            map = new int[n][m];
            Q = new LinkedList<>();
            visited = new boolean[20][20][1<<11];

            if (n + m == 0) break;
            int idx = 0 ;
            for (int i = 0; i < n; i++) {
                String s = br.readLine();
                for (int j = 0; j < m; j++) {
                    char now = s.charAt(j);
                    if(now == '.') map[i][j] = 0;
                    else if (now == '*') {
                        map[i][j] = ++idx;
                    } else if (now == 'x') {
                        map[i][j] = -1;
                    } else {
                        Q.add(new Point(i, j,0,0));
                    }

                }
            }
            System.out.println(T.bfs(idx));
        }

    }
}

1.

쓰레기가 있는 칸이라면 원래 더러운칸 방문 표시를 나타냈던
이전 마스크값에 현재 방문한 더러운칸을 or연산을 통해 방문했다고 표시해준다.

만약에 이전의 값이 1번째 , 2번째를 방문한 상태, 현재 방문한 더러운칸이 3번째칸이라고 가정해보자

0011 | (1 << 3-1) = 0011 | (1 << 2) = 0011 | 0100

최종적으로 0111 로 3번째까지 방문을 처리할수 있게 된다.

 if (map[nx][ny] > 0) { //쓰레기가 있는 칸이라면 마스크값 업데이트
                    nMask |= (1 << (map[nx][ny]-1));
                }

2.

처음에 visited 갯수를 new boolean[20][20][10] 으로 더러운칸의 최대갯수로 설정해줬는데 IndexOutofRange가 나왔다. 4개칸을 방문했다고 쳐도 1111 = 15로 10을 훌쩍 넘는값이어서 당연한 결과였다. 따라서 아래와같이 설정해줘야한다.
visited = new boolean[20][20][1<<11];

3.

모든 더러운칸을 방문했으면 리턴하도록 설정해줬다. 모든 더러운칸을 방문했다 함은 더러운칸 갯수만큼 1로 채워져있다는 것이다.
예를 들어 더러운칸이 총 4개가 있었다면 1111로 되어있으면 모든 칸을 방문했다는 의미이다.

idx = 4일때 1<<idx 값은 10000
따라서 10000에서 -1을 해주게 된다면 1111 의 결과를 얻을 수 있다.

if (mask == (1 << idx) - 1) {
                return d;
            }

🧩 Reference

• https://mygumi.tistory.com/361 [마이구미의 HelloWorld]