[백준] 1194 달이 차오른다, 가자.
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
2021-01-23
|
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
85
86
87
88
89
90
91
92
93
94
95
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main1194 {
static class Dal {
int x;
int y;
int key;
public Dal(int x, int y, int key) {
this.x = x;
this.y = y;
this.key = key;
}
}
public static int N, M, answer;
public static char arr[][];
public static Queue<Dal> q;
public static boolean vtd[][][], flag;
public static int dx[] = { -1, 0, 1, 0 };
public static int dy[] = { 0, -1, 0, 1 };
public static void solve() {
loop:while (!q.isEmpty()) {
int size = q.size();
while (size > 0) {
Dal tmp = q.poll();
int x = tmp.x;
int y = tmp.y;
int key = tmp.key;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == '#')
continue;
else if (!vtd[nx][ny][key]) {
if(arr[nx][ny] == '1') { // 탈출 하는 경우
flag = true;
answer++;
break loop;
}
if (arr[nx][ny] == '.' || arr[nx][ny] == '0') { // 그냥 일반적으로 지나갈 수 있는 통로
q.add(new Dal(nx, ny, key));
vtd[nx][ny][key] = true;
} else if (arr[nx][ny] >= 'A' && arr[nx][ny] <= 'F') {
if((key & (1 << (arr[nx][ny] - 'A'))) != 0) { //열쇠가 존재할 때
q.add(new Dal(nx, ny, key));
vtd[nx][ny][key] = true;
}
} else if (arr[nx][ny] >= 'a' && arr[nx][ny] <= 'f') {
int tmpKey = key | 1 << (arr[nx][ny] - 'a'); // 열쇠 보관
q.add(new Dal(nx, ny, tmpKey));
vtd[nx][ny][tmpKey] = true;
}
}
}
size--;
}
answer++;
}
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new char[N][M];
q = new LinkedList<>();
vtd = new boolean[N][M][1<<6]; // a - f : 0 - 5
answer = 0;
flag = false;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(bf.readLine());
String str = st.nextToken();
for (int j = 0; j < M; j++) {
arr[i][j] = str.charAt(j);
if (arr[i][j] == '0') {
q.add(new Dal(i, j, 0));
}
}
}
solve();
if(!flag) answer = -1;
System.out.println(answer);
}
}
|
cs |
#문제풀이
일반적인 bfs 탐색 문제이다. 특이한 점은 비트마스크를 이용하여야 한다.
문제에 나와있는 열쇠 (a - f) 와 문(A -F)는 각각 숫자 0 부터 5(문자 - 'a', 문자 - 'A')로 나타낼 수 있다.
또한, 쉬프트 연산자를 이용해서 (1 << (문자 - 'a'))를 해주면 각 키를 이진법으로 다음과 같이 나타낼 수 있다. 문 (대문자)도 마찬가지로 계산할 수 있다.
1 << ('a' - 'a') : 1
1 << ('b' - 'a') : 10
1 << ('c' - 'a') : 100
1 << ('d' - 'a') : 1000
1 << ('e' - 'a') : 10000
1 << ('f' - 'a') : 100000
이 때 비트 | (or) 연산자를 이용해서 키를 보관할 수 있다. 만약 a를 갖고 있는데 b 키를 갖을 수 있다면,
1 (1) | 2 (10) 을 하여 3(11)을 새로운 키로 갖고 다닐 수 있다.
만약 문을 만났을 때, 갖고 있는 열쇠 중에 맞는게 있는지 찾고 싶다면, 비트 & (and)연산자를 이용해서 키를 찾을 수 있다.
예를 들어 B 문을 만났을 때 b 키를 갖고 있는지 체크하려면, (key는 3이라고 가정)
key (11) & (1 << ('B' - 'A')) (10) => 2 (10)로 계산 할 수 있고, 0이 아니므로 키를 갖고 있는 것을 알 수 있다.