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;
}
}
}