문제
분석
미로의 구성이 아래와 같을 때, 미로를 탈출하는데 걸리는 최소 이동 횟수를 구하는 문제이다. (탈출 못하면 -1 출력)
빈 칸: 언제나 이동할 수 있다. ('.')
벽: 절대 이동할 수 없다. ('#')
열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
일반적인 최단거리를 구하는 문제는 상태에 단순히 위치만 저장해놓고 BFS를 진행하면 된다. 그러나 지금 문제는 문에 대응하는 열쇠를 가지고 있는 현황에 따라 같은 위치에 있더라도 다른 상황이 되고, 단순히 그 위치에 먼저 도착하는 것보다 키를 가지고 도착하는 것이 최종 최단거리에 부합하는 상황일 수 있다. 이를 위해서 visited 배열에 키 정보를 포함시켜야 한다.
키는 총 6개가 있는데, 키를 가지고 있는 상황이 총 2^6가지가 있다.
이를 위치 정보와 결합해 한 번에 표현하려면 visited[N][M][2][2][2][2][2][2]로 8차원 배열을 선언해야 한다. 이를 활용해서 BFS를 돌려도 해당 문제에서는 2초의 시간 제약과 128MB의 공간 제약으로 통과할 것으로 보인다.
그러나 6개의 키 정보를 비트마스크를 사용한다면 정수 하나로 표현할 수 있어서 더 효율적인 코드를 짤 수 있다.
숫자를 6자리 2진수로 변환하여 생각하면 각 자리마다 0과 1로 키를 가지고 있음을 표현할 수 있다. 따라서 2^6 = 64로 키 정보를 표현 가능하다.
1 << 6 에서 <<는 한 번 연산될 때마다 2배가 된다. 000000 부터 111111까지 표현할 것이므로 최종 visited[N][M][1 << 6]으로 정의된다.
BFS를 열쇠, 문, 빈 공간에 따라 진행하면 되는데, 해당 키를 가지고 있는지와 키를 추가하는 방법을 알아야 한다. (키와 문은 0~5로 변환해서 생각하여 이진수로 바꾼 것의 오른쪽부터 인덱스를 부여)
해당 키를 가지고 있는지 판단하려면 현재 키 정보와 필요한 키말고 다른 것들이 다 0인 비트와 & (AND) 연산을 했을 때 0이 아니면 해당 키를 가지고 있는 것으로 판단하면 된다.
키를 추가하는 것은 얻은 키와 현재 키 정보를 | (OR) 연산을 하면 키가 추가된다.
N이나 M (최대 50)만큼의 격자를 BFS로 탐색하고 키 상태에 따라 다르기 때문에 O(N×M×2^6)이 시간 복잡도이다.
코드
해결언어 : Java
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static char[][] grid;
static boolean[][][] visited;
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
grid = new char[N][M];
visited = new boolean[N][M][1 << 6];
int sx = -1, sy = -1;
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
grid[i][j] = input.charAt(j);
if (grid[i][j] == '0') {
sx = i;
sy = j;
}
}
}
System.out.println(bfs(sx, sy));
br.close();
}
static boolean in_range(int x, int y) {
return 0 <= x && x < N && 0 <= y && y < M;
}
static int bfs(int sx, int sy) {
Queue<int[]> q = new LinkedList<>();
visited[sx][sy][0] = true;
q.add(new int[] { sx, sy, 0, 0 });// x,y,key,d
while (!q.isEmpty()) {
int[] val = q.poll();
int x = val[0], y = val[1], key = val[2], d = val[3];
if (grid[x][y] == '1')
return d;
for (int i = 0; i < dx.length; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (in_range(nx, ny) && grid[nx][ny] != '#') {
int nxtKey = key;
if (Character.isUpperCase(grid[nx][ny])) {
int gate = grid[nx][ny] - 'A';
if ((key & (1 << gate)) == 0)
continue;
} else if (Character.isLowerCase(grid[nx][ny])) {
int k = grid[nx][ny] - 'a';
nxtKey = (key | (1 << k));
}
if (!visited[nx][ny][nxtKey]) {
visited[nx][ny][nxtKey] = true;
q.add(new int[] { nx, ny, nxtKey, d + 1 });
}
}
}
}
return -1;
}
}
