[Boj_17244] 아맞다우산

📎 문제 링크

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

 

▸ 문제

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

"아 맞다 우산!!!"

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

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

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

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

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

 

▸ 입력

첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)

두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.

비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.

챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

 

▸ 출력

S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 2
• 🔔  문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

아이템은 최대 5개까지 있을 수 있으므로, 2⁵ = 32가지 조합은 int형으로 충분히 표현할 수 있다.

따라서 경재 씨가 어떤 아이템을 챙겼는지를 비트마스크로 표현하여 문제를 해결했다.

 

입력을 처리하면서, 'X'로 표시된 아이템마다 0부터 순차적으로 번호를 부여했다.

예제 입력1을 그림으로 표현하면 아래와 같다.

이 번호들은 비트마스크의 각 자릿수로 사용되며, 왼쪽 시프트 연산 (1 << n)을 통해 비트상에서 해당 아이템을 표현할 수 있다.

 

아이템을 하나도 챙기지 않은 상태부터 모든 아이템을 챙긴 상태까지의 모든 조합을 고려해야 한다.
이때, 모든 아이템을 다 챙긴 상태는 전체 집합(공집합 제외)을 의미하므로 int checkNum = (1 << itemCnt) - 1로 설정한다.

이 값은 탐색 중 모든 아이템을 수집했는지 판단하는 기준이 된다.

 

탐색 중 아이템을 발견할 경우, 현재 아이템 상태에 OR 비트 연산 |을 사용해 새로운 아이템을 누적한다.

경재 씨가 0번 아이템을 소유하고 있고, 2번 아이템을 발견했을 때를 나타내면 아래와 같다.

 

경재 씨가 모든 아이템을 챙기고 최소 시간 내에 외출해야 하므로, 너비 우선 탐색(BFS)을 사용한다.

 

이때 같은 위치라도 현재까지 챙긴 아이템의 조합이 다를 수 있기 때문에, 단순히 위치만을 기준으로 방문 처리를 하면 안 된다.

예를 들어, 아래 그림처럼 경재 씨가 1번 아이템을 챙긴 뒤 다시 원래 왔던 길을 되돌아가야 하는 상황이 있다고 하자.

만약 2차원 배열로 방문 처리를 한다면, 이미 한 번 갔던 길은 다시 갈 수 없기 때문에 이런 경우를 처리하지 못하게 된다.

그래서 위치뿐 아니라 아이템 상태도 함께 고려한 3차원 방문 배열 checked = new boolean[m][n][checkNum+1]이 필요하다.

여기서 checkNum + 1로 설정한 이유는, checkNum은 가능한 아이템 상태 중 가장 마지막 값을 의미하고, 0부터 checkNum까지의 모든 상태를 저장하려면 총 checkNum + 1개의 공간이 필요하기 때문이다.

이 배열은 경재 씨가 (x, y) 위치에 어떤 아이템 상태로 도달했는지를 기록하는 데 사용된다.

 

BFS 탐색 중 출구 'E'에 도달했을 때, 현재 아이템 상태가 checkNum과 같다면 모든 물건을 챙긴 상태로 외출에 성공한 것이므로, 그때까지 걸린 시간을 반환하여 출력한다.

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 15792KB
시간 : 96ms

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

public class Main {
    static int n, m, itemCnt;
    static int[][] map;
    static boolean[][][] checked; // 위치, 챙긴 물건
    static Pos start;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static public class Pos {
        int x; int y; int cnt; int time;
        public Pos (int x, int y, int cnt, int time) {
            this.x = x; this.y = y;
            this.cnt = cnt; this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 가로
        m = Integer.parseInt(st.nextToken()); // 세로

        map = new int[m][n];
        for (int i = 0; i < m; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = str.charAt(j);
                // S : 경재 씨의 현재 위치
                // X : 챙겨야 하는 물건
                if (map[i][j] == 'S') {
                    start = new Pos(i, j, 0, 0);
                    map[i][j] = '.';
                } else if (map[i][j] == 'X') map[i][j] = itemCnt++;
            }
        }

        System.out.println(bfs());

        br.close();
    }

    private static int bfs() {
        Queue<Pos> que = new LinkedList<>();
        que.offer(start);

        int checkNum = (1 << itemCnt) - 1;
        checked = new boolean[m][n][checkNum+1];

        while (!que.isEmpty()) {
            Pos now = que.poll();

            // 나가는 문
            if (map[now.x][now.y] == 'E') {
                // 모든 아이템 획득
                if (checkNum == now.cnt) return now.time;
            }

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

                if (rangeCheck(nx, ny)) continue; // 범위 체크
                if (checked[nx][ny][now.cnt] || map[nx][ny] == '#') continue; // 이미 챙긴 물건, 벽 -> 이동 X

                // 다음 챙길 물건
                int nextItem = now.cnt;
                if (map[nx][ny] <= itemCnt) nextItem |= 1 << map[nx][ny];

                checked[nx][ny][nextItem] = true;
                que.offer(new Pos(nx, ny, nextItem, now.time+1));
            }
        }

        return -1;
    }

    private static boolean rangeCheck(int x, int y) {
        return x < 0 || x >= m || y < 0 || y >= n;
    }
}

 

예전에 비트 마스킹을 활용해 방문 체크를 하는 비슷한 문제를 풀었던 기억 덕분에 비교적 쉽게 문제를 풀 수 있었다.

비트 마스킹을 활용해 방문 체크를 하는 유형이 은근 많이 보이는 것 같다.

백준의 성곽, 로봇 청소기도 비슷한 문제니까 다시 한번 풀고 정리해야겠다 ! 👌🏻🌟