9328 key

์•Œ๊ณ ๋ฆฌ์ฆ˜(BFS, ๊ตฌํ˜„)

1. ๋ฐฉ๋ฌธํ•œ ๊ณณ์„ ์ฒดํฌํ•˜๋Š” check ์ด์ฐจ์› ๋ฐฐ์—ด, ํ‚ค๋ฅผ ์ €์žฅํ•˜๋Š” key ๋ฐฐ์—ด, ๋‹ซํžŒ๋ฌธ์„ ์ €์žฅํ•˜๋Š” closedDoor ๋ฒกํ„ฐ๊ฐ€ ํ•„์š”
2. ๋จผ์ € ํ‚ค ๋ฐฐ์—ด์€ 26๊ฐœ์˜ ์›์†Œ๋กœ ์ด๋ฃจ์–ด์ง„ bool ์ž๋ฃŒํ˜• ๋ฐฐ์—ด๋กœ ์„ ์–ธ. ๊ฐ ์•ŒํŒŒ๋ฒณ์— ํ•ด๋‹นํ•˜๋Š” ํ‚ค๊ฐ€ ๋“ค์–ด์˜ค๋ฉด 1์„ ์ €์žฅํ•œ๋‹ค.
3. ๋ฐฉ๋ฌธ๊ฐ€๋Šฅํ•œ์ง€ ์ฒดํฌํ•˜๋Š” checkCell ํ•จ์ˆ˜ ์„ ์–ธ
	-> ๋นˆ๊ณต๊ฐ„์ด๋ฉด true๋ฐ˜ํ™˜, ๋ฌธ์„œ๋ฉด ๋นˆ๊ณต๊ฐ„์œผ๋กœ ์ „ํ™˜ ํ›„ document 1์ฆ๊ฐ€ํ•˜๊ณ  true๋ฐ˜ํ™˜
	   ์†Œ๋ฌธ์ž๋ฉด ์—ด์‡  ์ถ”๊ฐ€ํ•˜๊ณ , ๋นˆ๊ณต๊ฐ„์œผ๋กœ ์ „ํ™˜ ํ›„ truw๋ฐ˜ํ™˜
	   ๋Œ€๋ฌธ์ž๊ณ , ์—ด์‡ ๊ฐ€ ์žˆ์œผ๋ฉด ๋นˆ๊ณต๊ฐ„์œผ๋กœ ์ „ํ™˜ ํ›„ true ๋ฐ˜ํ™˜
	   ๋Œ€๋ฌธ์ž๊ณ  ์—ด์‡ ๊ฐ€ ์—†์œผ๋ฉด closedDoor ๋ฒกํ„ฐ์— ํ•ด๋‹น์œ„์น˜ ์ถ”๊ฐ€ํ•˜๊ณ  false ๋ฐ˜ํ™˜
4. ์ฒ˜์Œ์— ํ…Œ๋‘๋ฆฌ ๋จผ์ € ๊ฒ€์‚ฌ
	-> ์ฒดํฌ ์•ˆ๋๊ณ , ๋ฒฝ์ด ์•„๋‹ˆ๊ณ , checkCell ํ†ต๊ณผํ•˜๋ฉด ํ•ด๋‹น ์œ„์น˜์—์„œ BFS ์‹œํ–‰
	-> ๋ชจ๋“  ํ…Œ๋‘๋ฆฌ ๊ฒ€์‚ฌ
5. ํ…Œ๋‘๋ฆฌ ๊ฒ€์‚ฌ ํ›„. cloesedDoor ๊ฒ€์‚ฌ
	-> ์ฒดํฌ ์•ˆ๋๊ณ , ๋นˆ๊ณต๊ฐ„ ์ „ํ™˜ ์•ˆ๋๊ณ , ์—ด์‡ ์žˆ์œผ๋ฉด ๋นˆ๊ณต๊ฐ„์œผ๋กœ ์ „ํ™˜ ํ›„ BFS ์‹œํ–‰
	-> ํ•œ๋ฒˆ์ด๋ผ๋„ BFS๊ฐ€ ์‹œํ–‰๋˜๋ฉด ๋‹ค์‹œ ์ฒ˜์Œ๋ถ€ํ„ฐ closedDoor๊ฒ€์‚ฌ๋ฅผ ํ•จ.
	-> BFS๊ฐ€ ์‹œํ–‰์•ˆ๋˜๋ฉด ๋ฃจํ”„ ์ค‘๋‹จ ํ›„ document ์ˆ˜ ์ถœ๋ ฅ

ํ‚ค ํฌ์ธํŠธ

1. ํ•œ๋ฒˆ ๊ฒ€์‚ฌํ•œ cell์€ ๋‹ค์‹œ ๊ฒ€์‚ฌํ•˜์ง€ ์•Š๋Š”๋‹ค. -> ๊ฒ€์‚ฌ์•ˆ๋œ ๊ณณ์€ ์—ด์‡ ๊ฐ€ ์—†์–ด์„œ ๋ชป๋“ค์–ด๊ฐ„ ๊ณณ์ด๋ฏ€๋กœ, closedDoor๋งŒ ๊ฒ€์‚ฌํ•˜๋ฉด ๋œ๋‹ค.
2. ์ž…๋ ฅ์ž˜๋ฐ›์ž !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

๋ฌธ์ž์—ด ์ž…๋ ฅ
	1. ๊ธธ์ด๋ฅผ ์ •ํ•ด์คฌ์„ ๋•Œ
		: ๋„์–ด์“ฐ๊ธฐ๋ฅผ ์•ˆํ–ˆ๋‹คํ•ด๋„, ๊ทธ๋ƒฅ map[i][j] ๋กœ ๋ฐ›์œผ๋ฉด ๋œ๋‹ค.
	2. ๊ธธ์ด๋ฅผ ์•ˆ์ •ํ•ด์คฌ์„ ๋–„
		: 	string temp;
			cin >> tmep;
			for(int i = 0; i<temp.length(); i++)
				key[i] = temp[i];
			๋กœ ๋ฐ›์ž

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <list>
#include <vector>
#include <string>
#define MAX_WIDTH 102
 
using namespace std;
 
typedef struct Location {
	int row;
	int col;
} Location;
 
char map[MAX_WIDTH][MAX_WIDTH];
bool key[27], check[MAX_WIDTH][MAX_WIDTH];
int width, height, document;
vector<Location> closedDoor;
 
void getMaxDocument();
void BFSfrom(int row, int col);
bool checkCell(int row, int col);
 
int main() {
	int numOfTC;
	cin >> numOfTC;
	for (int i = 0; i < numOfTC; i++) {
		memset(key, false, sizeof(key));
		cin >> height >> width;
		cin.ignore();
		for (int j = 0; j < height; j++) {
			for (int k = 0; k < width; k++)
				cin >> map[j][k];
		}
		string tempkey;
		cin >> tempkey;
 
		for (int j = 0; j < tempkey.length(); j++) {
			if (tempkey[j] == '0')
				break;
			key[tempkey[j] - 'a'] = true;
		}
 
		document = 0;
		getMaxDocument();
		cout << document << endl;
	}
}
//๋ชจ๋“  ๊ฒŒ์ดํŠธ๋กœ  ๋“ค์–ด๊ฐ -> ์—ด์ˆ˜ ์žˆ๋Š” ๋ฌธ์€ ์—ด๊ณ  . ๋กœ ๋ฐ”๊พธ๊ณ  ์•ˆ์œผ๋กœ ๋“ค์–ด๊ฐ. ์—ด์‡ ๋“  ๋ฌธ์„œ๋“  ์ฃผ์œผ๋ฉด .์œผ๋กœ ๋ฐ”๊ฟˆ
	//์—ด์ˆ˜ ์—†๋Š” ๋ฌธ์€ closedDoor์— ์ถ”๊ฐ€
	//๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณณ BFS๊ฐ€ ๋๋‚˜๋ฉด, closedDoor ๊ฒ€์‚ฌ ์ˆ˜ํ–‰. ์ƒˆ๋กœ ์—ด๋ฆฐ ๊ณณ์„ ๊ธฐ์ค€์œผ๋กœ ๋‹ค์‹œ BFS ์‹œํ–‰ ์—ด๋ฆฐ ๊ณณ์ด ์—†์œผ๋ฉด ๊ทธ๋•Œ์˜ count ๋ฐ˜ํ™˜
void getMaxDocument() {
	//๋ชจ๋“  ๊ฒŒ์ดํŠธ ๊ฒ€์‚ฌ. ๊ฒŒ์ดํŠธ๊ฐ€ ์ด์–ด์ง€๋Š” ๊ฒฝ์šฐ ๊ณ ๋ ค
	for (int i = 0; i < width; i++) {
		if (!check[0][i] && map[0][i] != '*' && checkCell(0, i))
			BFSfrom(0, i);
	}
	for (int i = 0; i < width; i++) {
		if (!check[height - 1][i] && map[height - 1][i] != '*' && checkCell(height - 1, i))
			BFSfrom(height - 1, i);
	}
	for (int i = 1; i < height - 1; i++) {
		if (!check[i][0] && map[i][0] != '*' && checkCell(i, 0))
			BFSfrom(i, 0);
	}
	for (int i = 1; i < height - 1; i++) {
		if (!check[i][width - 1] && map[i][width - 1] != '*' && checkCell(i, width - 1))
			BFSfrom(i, width - 1);
	}
 
	//closedDoor ๊ฒ€์‚ฌ
	bool loopCheck = true;
	while (loopCheck) {
		loopCheck = false;
		int length = closedDoor.size();
		for (int i = 0; i < length; i++) {
			if (!check[closedDoor[i].row][closedDoor[i].col] && map[closedDoor[i].row][closedDoor[i].col] != '.' && key[map[closedDoor[i].row][closedDoor[i].col] - 'A']) {
				map[closedDoor[i].row][closedDoor[i].col] = '.';
				BFSfrom(closedDoor[i].row, closedDoor[i].col);
				loopCheck = true;
			}
		}
	}
 
	memset(check, 0, sizeof(check));
	memset(key, 0, sizeof(key));
	closedDoor.clear();
	memset(map, 0, sizeof(map));
}
 
void BFSfrom(int row, int col) {
	list<Location> q;
	q.push_back({ row, col });
	check[row][col] = true;
 
	while (!q.empty()) {
		Location temp = q.front();
		q.pop_front();
 
		if (temp.row > 0 && !check[temp.row - 1][temp.col] && map[temp.row - 1][temp.col] != '*') {
			if (checkCell(temp.row - 1, temp.col)) {
				check[temp.row - 1][temp.col] = true;
				q.push_back({ temp.row - 1, temp.col });
			}
		}
		if (temp.col < width - 1 && !check[temp.row][temp.col + 1] && map[temp.row][temp.col + 1] != '*') {
			if (checkCell(temp.row, temp.col + 1)) {
				check[temp.row][temp.col + 1] = true;
				q.push_back({ temp.row, temp.col + 1 });
			}
		}
		if (temp.row < height - 1 && !check[temp.row + 1][temp.col] && map[temp.row + 1][temp.col] != '*') {
			if (checkCell(temp.row + 1, temp.col)) {
				check[temp.row + 1][temp.col] = true;
				q.push_back({ temp.row + 1, temp.col });
			}
		}
		if (temp.col > 0 && !check[temp.row][temp.col - 1] && map[temp.row][temp.col - 1] != '*') {
			if (checkCell(temp.row, temp.col - 1)) {
				check[temp.row][temp.col - 1] = true;
				q.push_back({ temp.row, temp.col - 1 });
			}
		}
	}
}
 
bool checkCell(int row, int col) {
	if (map[row][col] == '.')
		return true;
	else if (map[row][col] == '$') {
		map[row][col] = '.';
		document++;
		return true;
	}
	else if (map[row][col] >= 'a' && map[row][col] <= 'z') {
		key[map[row][col] - 'a'] = true;
		map[row][col] = '.';
		return true;
	}
	else if(map[row][col] >= 'A' && map[row][col] <='Z'){
		if (key[map[row][col] - 'A']) {
			map[row][col] = '.';
			return true;
		}
		else {
			closedDoor.push_back({ row, col });
			return false;
		}
	}
}