백준 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분정도밖에 안찾았다 ㅎㅎ;;