[백준 9328] 열쇠

고통스러웠다..

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

9328번: 열쇠

#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
int T;
int R, C;
int key_bit[26];
char board[100 + 3][100 + 3];
int dollar;
int max_dollar;


struct _st
{
	int key_num;
	bool key_array[26] = { false, };
};

_st Info[1];	// 전역 키 정보 


struct _qt
{
	int x, y;
};
std::queue<_qt> Q;
int visited[100 + 3][100 + 3];


void make_key_bit()
{
	for (int i = 0; i < 26; i++) {
		key_bit[i] = pow(2, i);
	}
}


void init()
{
	memset(board, 0, sizeof(board));
	memset(Info, 0, sizeof(Info));
	max_dollar = 0;
}


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
	}

	// 초기 키 정보
	char in[26 + 2];
	scanf("%s", &in);
	if (in == "0")  return;
	for (int i = 0; ; i++) {
		if (in[i] == '\0') break;
		Info[0].key_num += key_bit[in[i] - 'a'];
		Info[0].key_array[in[i] - 'a'] = true;
	}
}


void make_bound()	// 어디든 갈 수 있도록 bound 만듦 
{
	for (int i = 0; i <= R + 1; i++) {
		for (int j = 0; j <= C + 1; j++) {
			if (i == 0 || i == R + 1 || j == 0 || j == C + 1) board[i][j] = '.';
		}
	}
}


bool get_new_key()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	// init
	memset(visited, 0, sizeof(visited));
	Q = {};

	//for (int i = 0; i < 26; i++) printf("%d ", Info[0].key_array[i]);
	//printf("\n");

	Q.push({ 0, 0 });
	visited[0][0] = 1;
	dollar = 0;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R + 1 || ny < 0 || ny > C + 1) continue;	// 영역 밖 스루
			if (board[nx][ny] == '*') continue;	// 벽이면 스루
			if (visited[nx][ny]) continue;

			// 열쇠 
			if (board[nx][ny] >= 'a' && board[nx][ny] <= 'z') {
				int k = board[nx][ny] - 'a';
				if (Info[0].key_array[k] == false) {
					Info[0].key_num += key_bit[k];
					Info[0].key_array[k] = true;
					return true;
				}
				else if (Info[0].key_array[k] == true) {
					Q.push({ nx, ny });
					visited[nx][ny] = 1;
				}
			}
			// 빈칸
			else if (board[nx][ny] == '.') {
				Q.push({ nx, ny });
				visited[nx][ny] = 1;
			}
			// 문
			else if (board[nx][ny] >= 'A' && board[nx][ny] <= 'Z') {
				int have = board[nx][ny] - 'A';
				if (Info[0].key_array[have] == true) {
					Q.push({ nx, ny });
					visited[nx][ny] = 1;
				}
			}
			// 문서
			else if (board[nx][ny] == '$') {
				dollar++;
				Q.push({ nx ,ny });
				visited[nx][ny] = 1;
			}
		}
	}
	return false;
}


void Flood_Fill()
{
	bool stop = false;
	while (1) {
		if (!get_new_key()) stop = true;
		if (max_dollar < dollar) max_dollar = dollar;
		if (stop == true) return;
	}
}


int main()
{
	scanf("%d", &T);
	make_key_bit();
	for (int t = 0; t < T; t++) {
		init();
		input();
		make_bound();
		Flood_Fill();
		printf("%d\n", max_dollar);
	}
	return 0;
}

 

1. 처음에는 BFS에서 돌리는 Q 구조체 안에 키 정보까지 넣어서 관리해주었더니 시간초과 났다. 

struct _qt
{
	int x, y;
    int key_num;
    bool key_array[26] = {false, };
}

이런식으로 구조체 만들었었다. 절대 이렇게 하면 안된다. 

=> 이걸 개선하기 위해 가지고 있는 키 정보를 전역으로 선언하고, 상태가 발전될 때 마다 해당 정보를 갱신해주었다. 

 

2. "지도 안팎을 드나들 수 있다"는 조건을 위해 가장자리에 반드시 갈 수 있는 빈칸 board[][] = '.' 을 만들어 주었다. 

3. 탐색을 시도할 때 마다 줍는 문서의 개수가 다르므로, BFS 탐색 종료 후 최대값을 비교해주어야 했다. 

4. 지도를 탐색하다가 새로운 열쇠를 주우면 현재 탐색을 종료하고, 다시 처음부터(0, 0) 더 갈 수 있는곳이 있는지 탐색한다. 이때 실수했던 것은 열쇠를 줍긴 했는데 기존에 가지고 있는 열쇠와 동일할 때는, 종료하지 않고 탐색을 계속 해주어야 한다는 것이다.