백준(BOJ) 1194번 달이 차오른다, 가자.

문제 :

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

1194번: 달이 차오른다, 가자.

 

풀이 :

BFS문제이고 비트 마스킹으로 푼다면 쉽게 풀 수 있는 문제였습니다.

 

1 << 0 은 1이기에 a 키를

1 << 1 은 2이기에 b 키를

1 << 2 는 3이기에 c 키를 

.

.

 

1 << 6 은 32이고 f 키를 타나 낸다면 해당하는 키들을 가진채 큐 안에서 움직일 수 있습니다.

 

 

코드 ( C++ )

	#include <cstring>
	#include <queue>
	#include <iostream>
	#include <algorithm>
	#include <vector>
	using namespace std;
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	int n, m;
	//d[][][0] 은 아무 열쇠도 안가진 상태
	int d[51][51][1 << 7];
	char a[51][51];
	int key[27];
	struct g {
	int y, x;
	int key;
	};
	int bfs(int i, int j)
	{
	queue<g> q;
	memset(d, -1, sizeof(d));
	for (int k = 0; k < 4; ++k) {
	q.push({ i,j,0 });
	d[i][j][0] = 0;
	}
	bool check = false;
	int ret = -1;
	while (!q.empty()) {
	int y = q.front().y;
	int x = q.front().x;
	int ke = q.front().key;
	q.pop();
	for (int k = 0; k < 4; ++k) {
	int ny = y + dy[k];
	int nx = x + dx[k];
	int nextke = ke;
	if (a[ny][nx] == '1') {
	return d[y][x][ke] + 1;
	}
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) continue;
	if (d[ny][nx][nextke] != -1) continue;
	if (a[ny][nx] == '#') continue;
	if ('A' <= a[ny][nx] && a[ny][nx] <= 'F') {
	int cnt = a[ny][nx] - 'A';
	int cand = nextke;
	// key가 없으면 가지 못함
	if ((cand &= (1 << cnt)) == 0) continue;
	}
	if ('a' <= a[ny][nx] && a[ny][nx] <= 'f') {
	int cnt = a[ny][nx] - 'a';
	// key를 추가
	nextke |= (1 << cnt);
	}
	q.push({ ny,nx,nextke});
	d[ny][nx][nextke] = d[y][x][ke] + 1;
	}
	if (check) break;
	}
	return ret;
	}
	int main() {
	cin >> n >> m;
	int fy, fx;
	for(int i=0; i<n; ++i)
	for (int j = 0; j < m; ++j) {
	cin >> a[i][j];
	if (a[i][j] == '0') {
	fy = i;
	fx = j;
	}
	}
	cout << bfs(fy, fx) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub