BOJ 1194 - 달이 차오른다, 가자

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

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

제약조건(열쇠,문)이 추가된 플러드필 문제이다

 

처음엔 큐에 방문노드위치(cy,cx)와 비트마스크를 이용한 현재 key, 그리고 visited배열을 넘겨주면서 열쇠를 먹으면 false로 초기화된 visited를 다음 큐에 넣어주는 식으로 짜봤는데 메모리 초과가 나왔다..ㅜㅜ

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <tuple>
#include <utility>
using namespace std;
typedef tuple < pair<int, int>, int, vector<vector<bool>>> P;
const int dy[4]{ 0,0,-1,1 };
const int dx[4]{ 1,-1,0,0 };

int n, m;
char map[51][51];

int main() {
	scanf("%d %d", &n, &m); getchar();
	int sy, sx;
	vector<vector<bool>> v(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			v[i].push_back(false);
			scanf("%1c", &map[i][j]);
			if (map[i][j] == '0') {
				sy = i, sx = j;
				v[i][j] = true;
			}
		}
		getchar();
	}

	queue<P> q;
	q.push({ {sy,sx},0,v });
	int len = 0;
	bool flag = false;	
	while (!q.empty()) {
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			P curr = q.front();
			q.pop();
			int cy = get<0>(curr).first, cx = get<0>(curr).second;
			int ckey = get<1>(curr);
			vector<vector<bool>> cvisited = get<2>(curr);

			if (map[cy][cx] == '1') {
				flag = true;
				break;
			}

			for (int i = 0; i < 4; i++) {
				int ny = cy + dy[i], nx = cx + dx[i];
				int nkey = ckey;
				vector<vector<bool>> nvisited = cvisited;
				if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
				if (nvisited[ny][nx] || map[ny][nx] == '#') continue;

				//다음 탐색 할 곳이 열쇠라면
				if (map[ny][nx] >= 'a' && map[ny][nx] <= 'f') {
					for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) nvisited[i][j] = false;
					nvisited[ny][nx] = true;
					nkey |= 1 << (map[ny][nx] - 'a');
					q.push({ {ny,nx}, nkey, nvisited });
				}
				//다음 탐색하는 곳이 문이라면
				else if (map[ny][nx] >= 'A' && map[ny][nx] <= 'F') {
					//키가 있으면 방문가능
					if (nkey & (1 << (map[ny][nx] - 'A'))) {
						nvisited[ny][nx] = true;
						q.push({ {ny,nx},nkey,nvisited });
					}
				}
				//다음 탐색하는 곳이 .빈공간 // 시작점 // 끝점
				else {
					nvisited[ny][nx] = true;
					q.push({ {ny,nx},nkey,nvisited });
				}
			}//end 사방탐색
		}//end 작은큐
		len++;
		if (flag) break;
	}//end bfs

	printf("%d\n", (flag ? len - 1 : -1));

}

코드가 조금 난잡하긴 해도 ac받을줄 알았는데 아쉽다.

 

풀이는 라이님의 코드를 참고했다. (사실 참고했다고 언급하지 않은 문제중에도 참고한 것이 있을...)

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <tuple>
#include <utility>
using namespace std;
const int dy[4]{ 0,0,-1,1 };
const int dx[4]{ 1,-1,0,0 };

int n, m;
char map[51][51];
bool visited[51][51][1 << 6];

int main() {
	scanf("%d %d", &n, &m); getchar();
	int sy, sx;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1c", &map[i][j]);
			if (map[i][j] == '0') {
				sy = i, sx = j;
			}
		}
		getchar();
	}

	queue<tuple<pair<int,int>,int>> q;
	q.push({ {sy,sx},0 });
	visited[sy][sx][0] = true;
	int len = 0;
	bool flag = false;	
	while (!q.empty()) {
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			auto curr = q.front();
			q.pop();
			int cy = get<0>(curr).first, cx = get<0>(curr).second;
			int ckey = get<1>(curr);

			if (map[cy][cx] == '1') {
				flag = true;
				break;
			}

			for (int i = 0; i < 4; i++) {
				int ny = cy + dy[i], nx = cx + dx[i];
				int nkey = ckey;
				if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
				if (visited[ny][nx][nkey] || map[ny][nx] == '#') continue;

				//다음 탐색 할 곳이 열쇠라면
				if (map[ny][nx] >= 'a' && map[ny][nx] <= 'f'){
					nkey |= 1 << (map[ny][nx] - 'a');
					visited[ny][nx][nkey] = true;
					q.push({ {ny,nx}, nkey});
				}
				//다음 탐색하는 곳이 문이라면
				else if (map[ny][nx] >= 'A' && map[ny][nx] <= 'F') {
					//키가 있으면 방문가능
					if (nkey & (1 << (map[ny][nx] - 'A'))) {
						visited[ny][nx][nkey] = true;
						q.push({ {ny,nx},nkey});
					}
				}
				//다음 탐색하는 곳이 .빈공간 // 시작점 // 끝점
				else {
					visited[ny][nx][nkey] = true;
					q.push({ {ny,nx},nkey});
				}
			}//end 사방탐색
		}//end 작은큐
		len++;
		if (flag) break;
	}//end bfs

	printf("%d\n", (flag ? len - 1 : -1));

}

큐에는 현재 위치와 키현황만 넘겨준다. visited에는 차원을 하나 더해서 key상태마다 visited를 배정했다.

 

 

ps.이정도 난이도의 비트마스크문제를 많이 풀어보는게 좋을 것 같다.