백준 1194: 달이 차오른다, 가자.
달이 차오른다, 가자. 성공
| 2 초 | 128 MB | 11811 | 4627 | 3111 | 36.437% |
문제
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 칸: 언제나 이동할 수 있다. ('.')
- 벽: 절대 이동할 수 없다. ('#')
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
예제 입력 1 복사
1 7
f0.F..1
예제 출력 1 복사
7
예제 입력 2 복사
5 5
....1
#1###
.1.#0
....A
.1.#.
예제 출력 2 복사
-1
예제 입력 3 복사
7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1
예제 출력 3 복사
55
예제 입력 4 복사
3 4
1..0
###.
1...
예제 출력 4 복사
3
예제 입력 5 복사
3 5
..0..
.###.
..1.A
예제 출력 5 복사
6
예제 입력 6 복사
4 5
0....
.#B#A
.#.#.
b#a#1
예제 출력 6 복사
19
예제 입력 7 복사
1 11
c.0.C.C.C.1
예제 출력 7 복사
12
예제 입력 8 복사
3 6
###...
#0A.1a
###...
예제 출력 8 복사
-1
출처
문제 푸는법 ㅋ-ㅋ
000000
a라면 a-'a'하면 0이다
1을 왼쪽으로 a-'a'만큼 shift하면
000001된다.
!!!!!! 그 다음
b를 발견해서 가지고 있는 키가 ab라면
000011이 되어야하는데
현재
000001이고
000010이랑 합쳐야한다
그럼 다시
b -'a'==1이고
1을 다시 왼쪽으로 b-'a'만큼 shift하면
000010이 된다.
그러현 현재 key값과 (OR) 연산을 하면
000011이 된다.
열쇠를 갖고 있는지에 대한 비교는
현재 키가
b를 가진 상태에서
000011 b와 비교하면
000010 비교를 한다
&연산
000010 이러면 b를 갖고 있다는 말을 의미한다.
만약 B를 갖고있지않은 상태에서
011101
000010
&연산으로 비교를 하면
000000
즉 0이 된다.
이런방식을 비트마스킹에 적용하면 된다.
#include<iostream>
#include<queue>
#include<cmath>
#include<string>
using namespace std;
struct info {
int y, x, cnt, key;
};
char Map[50][50];
bool visited[50][50][64] = { false, };//마지막은 [64]로 해도 똑같다.
int n, m;
int sy, sx;//출발점
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool hasKey(int key, char ch) {
int R_value = key & (1 << ch - 'A');
if (R_value != 0)return true;
return false;
}
int bfs() {
queue<info> q;
q.push({ sy,sx,0,0 });
visited[sy][sx][0] = true;
while (!q.empty()) {
int y = q.front().y;
int x = q.front().x;
int cnt = q.front().cnt;
int key = q.front().key;
q.pop();
if (Map[y][x] == '1') {
return cnt;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < n && nx < m && ny >= 0 && nx >= 0) {
if (visited[ny][nx][key] == false) {
if (Map[ny][nx] == '1' || Map[ny][nx] == '.') {
q.push({ ny,nx,cnt + 1,key });
visited[ny][nx][key] = true;
}
else if (Map[ny][nx] >= 'a' && Map[ny][nx] <= 'f') {//소문자일때
int add_key = key | (1 << Map[ny][nx] - 'a');
q.push({ ny,nx,cnt + 1,add_key });
visited[ny][nx][add_key] = true;
}
else if (Map[ny][nx] >= 'A' && Map[ny][nx] <= 'F') {//대문자 일때
//현재키와 비교할 대문자가 있나 확인
if (hasKey(key, Map[ny][nx])) {
q.push({ ny, nx, cnt + 1, key });
visited[ny][nx][key] = true;
}
}
}
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> Map[i][j];
if (Map[i][j] == '0') {
sy = i, sx = j;
Map[i][j] = '.';
}
}
}
cout << bfs();
return 0;
}근데 자꾸 메모리가 터져서 봤더니 visited[ny][nx][cnt]에 하나라도 방문처리를 해주지 않으면 q가 엄청나게 생성되고 pop()은 되지않아서 큰 메모리가 소모된다. 다행이다 그래도 40분정도밖에 안찾았다 ㅎㅎ;;