[G1] 백준 1194번 달이 차오른다, 가자. C++ 너비 우선 탐색, 비트 마스킹

리뷰

 

https://www.acmicpc.net/problem/1194

벽 부수고 이동하기의 상위 호환처럼 느껴진 문제

열쇠 먹고 문따는 문제는 풀어야지 풀어야지 하다가 처음으로 접해보았다.

예상 못한 엣지케이스가 있어 한번에 AC를 받진 못했지만, 그리 어렵게 느껴지진 않은 문제

 

 

전역 변수

• A : 문을 만났을 때 key값 계산을 편하게 하기 위한 문자형 상수 변수
• a : 키를 만났을 때 key값 계산을 편하게 하기 위한 문자형 상수 변수
• n : 맵의 세로 크기를 저장할 변수
• m : 맵의 가로 크기를 저장할 변수
• sx, sy : 시작 위치의 x, y좌표를 저장할 변수
• lst : 맵 정보를 입력 받아 저장할 문자열 배열
• v : 키 상태를 기준으로 맵 방문 여부를 체크하기 위한 방문 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : BFS을 실행할 때 x, y좌표와 걸린 시간 t, 현재 키 값 k를 정의하기 위한 구조체

 

함수

1. bfs

int bfs()

 

너비 우선 탐색을 통해 맵을 탈출할 수 있는 가장 빠른 시간을 구하기 위한 함수

1. Pos타입의 큐 q를 초기화 하고, 초기 위치 sx, sy를 입력한다, 시간과 키값은 디폴트값 0이다.
2. 마찬가지로 시작 위치 및 키 값이 0인 좌표에 방문처리를 진행해 준다.
3. q가 빌 때 까지 while루프를 수행하며 매 루프마다 요소를 한개씩 빼내어 준다.
4. 4방향 탐색을 진행하고 맵의 범위를 벗어나지 않고 벽이 아니라면 이동을 진행해 준다.
5. 만약 이동한 위치가 이미 현재 키값으로 방문처리가 되어 있다면 continue 처리해 준다.
6. 이동할 곳이 맵에서 '.'라면 현재 키값 그대로 방문표시 후 시간을 증가시켜 이동해 준다.
7. 열쇠라면 두가지 경우로 나뉜다, 우선 변수 key에 2^lst[nx][ny] - a 값을 저장해 준다. (비트 마스킹)
8. 만약 ck와 key를 비트연산한 값이 true라면 키값 그대로 방문표시 후 시간을 증가시켜 이동해 준다.
9. false라면 ck에 key만큼 더해주고, 해당 키값으로 방문처리 후 새로운 키값과 시간을 증가시켜 이동해 준다.
10. 이동할 곳이 맵에서 문이라면 마찬가지로 변수 key에 2^lst[nx][ny] - A 값을 저장해 준다. (비트 마스킹)
11. 만약 ck와 key를 비트연산한 값이 true라면 키를 보유중이므로 이동 처리를 진행해 준다.
12. 이동할 곳이 맵에서 '1'이라면 현재 시간 + 1을 한 값을 리턴해 주고 탐색을 종료한다.
13. while루프가 종료될 때 까지 시간을 리턴하지 못했다면 -1을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, n크기의 맵에 맵 정보를 입력 받아준다. (문자열)
2. 매 줄을 입력 받을 때 각 문자를 체크한다.
3. 만약 값이 '0'일 경우 sx, sy에 i, j값을 저장해 준다.
4. 편한 시뮬레이션을 하기 위해 '0'을 '.'로 변경해 준다.
5. bfs함수를 실행하고 받은 리턴값을 출력해 준다.

 

트러블 슈팅

1. 키를 한번 더 먹는 엣지 케이스가 발생하였다, 키를 먹을때 조건을 둘로 나누어 주어 해결하였다.
2. 방문 처리를 매 조건문 마다 실행했더니 메모리 초과가 출력되었다, 최초 한번으로 변경하니 AC를 받았다.

 

참고 사항

• 이동 조건 체크는 맵 범위 내이면서 벽이 아닐 경우만 진행해 준다.
• 이후 조건에 따라 이동 여부를 체크해 주면 된다, 초기 시작 위치 '0'은 '.'로 바꾸어주면 편하다.
• 맵에 존재하는 키가 총 6개 이므로 비트마스킹을 체크할 범위는 2^6 - 1로 세팅해 주면 된다.
• 변수 a, A처럼 상수 문자열을 통해 key값을 편하게 파싱해 주는 것이 편하다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

const char A = 'A';
const char a = 'a';
int n, m, sx, sy;
string lst[50];
bool v[50][50][64];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y, t, k;
};

int bfs() {
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	v[sx][sy][0] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, ck = pos.k;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != '#') {
				if (v[nx][ny][ck]) continue;

				if (lst[nx][ny] == '.') {
					v[nx][ny][ck] = 1;
					q.push({ nx, ny, nt, ck });
				}
				else if (lst[nx][ny] >= 'a') {
					int key = pow(2, lst[nx][ny] - a);
					if (ck & key) {
						v[nx][ny][ck] = 1;
						q.push({ nx, ny, nt, ck });
					}
					else {
						v[nx][ny][ck + key] = 1;
						q.push({ nx, ny, nt, ck + key });
					}
				}
				else if (lst[nx][ny] >= 'A') {
					int key = pow(2, lst[nx][ny] - A);
					if (ck & key) {
						v[nx][ny][ck] = 1;
						q.push({ nx, ny, nt, ck });
					}
				}
				else if (lst[nx][ny] == '1') return nt;
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		for (int j = 0; j < m; ++j) {
			if (lst[i][j] == '0') {
				sx = i, sy = j;
				lst[i][j] = '.';
			}
		}
	}
	cout << bfs();
}