[백준]1194: 달이 차오른다, 가자 - JAVA
[백준]1194: 달이 차오른다, 가자
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
풀이
🪑 BFS + 비트마스킹이 결합된 문제이다! 재밌었던 문제였다. 특히 열쇠를 가지고 있는지 여부를 하나씩 계산해 주다가 비트마스킹으로 간편하게 확인할 수 있는 방법을 알게 되고 너무 신세계였다.
📝 문제의 조건을 정리해 보자!
- 주어진 미로를 탈출하는데 걸리는 최소 이동 횟수를 구한다.
- 0에서 출발하여 1로 탈출한다
- 문은 대응하는 열쇠를 먼저 얻어야 열 수 있다.
- 같은 타입의 열쇠가 여러개 존재할 수 있다.
🔧 문제를 풀어보자!
- 최소 이동 횟수를 구하므로 BFS를 사용한다.
- 방문체크가 중요하다. 방문체크시 열쇠의 소유 여부를 함께 체크한다.
- 탐색 중에 열쇠를 만나면 해당 열쇠를 현재 열쇠 정보에 추가해 준다.
- 탐색 중에 문을 만나면 해당 문에 맞는 열쇠를 가지고 있는지 확인한 후 탐색한다.
🔹 BFS를 사용한다.
- 최소 이동 횟수 즉, BFS문제이다.
🔹 방문체크시 열쇠의 소유 여부를 함께 체크한다.
- 어떻게 소유 여부를 체크해 줄 수 있을지 고민하다가, 리눅스의 권한 관리가 떠올랐다. 권한에 대한 정보를 숫자로 표현하였고, 나도 여기에서 힌트를 얻어 다음과 같이 표현하였다.
- 열쇠 a는 2의 0제곱 -> 1
- 열쇠 b는 2의 1제곱 -> 2
- 열쇠 c는 2의 2제곱 -> 4
- 열쇠 d는 2의 3제곱 -> 8
- 열쇠 e는 2의 4제곱 -> 16
- 열쇠 f는 2의 5제곱 -> 32
모든 열쇠를 다 가지고 있다면 63이된다. 그러므로 방문 체크 할 배열의 크기를 64로 제한해 주었다.
🙋♀️ 위와 같은 방식으로 하면 문제점이 있다. 문을 만났을때 문에 맞는 열쇠를 가지고 있는지 확인하는 과정이 까다롭다.
그래서 위의 방식을 비트 표현 방식으로 변경해 주었다.
- 열쇠 a -> 000001
- 열쇠 b -> 000010
- 열쇠 c -> 000100
- 열쇠 d -> 001000
- 열쇠 e -> 010000
- 열쇠 f -> 100000
이렇게 표현하면 비트를 숫자로도 표현할 수 있으며 해당 비트가 1인지 0인지 비트연산을 통해 확인하여 열쇠 소유 여부를 빠르게 확인할 수 있다.
🔹 탐색 중에 열쇠를 만나면 해당 열쇠를 현재 열쇠 정보에 추가해 준다.
- 열쇠에 종류에 따라 1의 쉬프트 연산을 해준다.
- 쉬프트 연산을 해 주어 얻은 새로운 열쇠의 정보를 현재 가지고 있는 key값과 OR연산하여 새로운 열쇠 정보를 기존의 key에 더해주고 탐색을 진행하면 된다.
🔹 탐색 중에 문을 만나면 해당 문에 맞는 열쇠를 가지고 있는지 확인한 후 탐색한다.
- 해당 열쇠에 해당하는 비트가 1인지만 확인하면 된다.
- 만난 문의 종류에 따라 1의 쉬프트 연산을 해준다.
- 해당 비트의 값과 현재 key값을 AND 연산으로 비교한다. AND연산은 연산하는 두 값의 비트가 모두 1이어야 1을 반환하므로 1인지 확인한다.
- 이때 결과는 001000등 비트로 확인되므로 이 값을 정수로 변환하여 현재 열고자 하는 문에 해당하는 열쇠 정보가 8인지만 확인해 주면 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
//1944: 복제 로봇
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static char[][] board;
static Node start;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) throws IOException {
//입력
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str = bf.readLine();
StringTokenizer st = new StringTokenizer(str);
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
board = new char[n][m];
for(int i = 0; i < n; i++) {
str = bf.readLine();
for(int j = 0; j < m; j++) {
char c = str.charAt(j);
board[i][j] = c;
if(c == '0') start = new Node(i, j, 0, 0);
}
}
//입력 끝
System.out.println(bfs());
}
public static int bfs() {
Queue<Node> q = new LinkedList<>();
boolean[][][] visited = new boolean[n][m][64]; //열쇠 가지고 방문 여부 체크.
q.offer(start);
visited[start.x][start.y][0] = true;
while(!q.isEmpty()) {
Node current = q.poll();
if(board[current.x][current.y] == '1') return current.cost;
for(int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(visited[nx][ny][current.key] || board[nx][ny] == '#') continue;
if(board[nx][ny] >= 'a' && board[nx][ny] <= 'f') { //열쇠
int next_key = 1 << (board[nx][ny] - 'a');
next_key = current.key | next_key;
visited[nx][ny][next_key] = true;
q.offer(new Node(nx, ny, current.cost + 1, next_key));
}
else if(board[nx][ny] >= 'A' && board[nx][ny] <= 'F') { //문
if((current.key & 1 << (board[nx][ny] - 'A')) == (int)Math.pow(2, board[nx][ny] - 'A')) { //해당 비트가 켜져있는지 확인
visited[nx][ny][current.key] = true;
q.offer(new Node(nx, ny, current.cost + 1, current.key));
}
} else {
visited[nx][ny][current.key] = true;
q.offer(new Node(nx, ny, current.cost + 1, current.key));
}
}
}
return -1;
}
public static class Node {
int x, y, cost, key;
public Node(int x, int y, int cost, int key) {
this.x = x;
this.y = y;
this.cost = cost;
this.key = key;
}
}
}
|
cs |