BOJ 9328. μ΄μ
πββοΈ[Gold I] μ΄μ - 9328
μ±λ₯ μμ½
λ©λͺ¨λ¦¬: 2168 KB, μκ°: 248 ms
λΆλ₯
λλΉ μ°μ νμ, κ·Έλν μ΄λ‘ , κ·Έλν νμ, ꡬν
μ μΆ μΌμ
2024λ 3μ 12μΌ 14:56:59
λ¬Έμ μ€λͺ
μκ·Όμ΄λ 1μΈ΅ λΉλ©μ μΉ¨μ ν΄ λ§€μ° μ€μν λ¬Έμλ₯Ό νμ³μ€λ €κ³ νλ€. μκ·Όμ΄κ° κ°μ§κ³ μλ νλ©΄λμλ λ¬Έμμ μμΉκ° λͺ¨λ λνλ μλ€. λΉλ©μ λ¬Έμ λͺ¨λ μ 겨μκΈ° λλ¬Έμ, λ¬Έμ μ΄λ €λ©΄ μ΄μ κ° νμνλ€. μκ·Όμ΄λ μΌλΆ μ΄μ λ₯Ό μ΄λ―Έ κ°μ§κ³ μκ³ , μΌλΆ μ΄μ λ λΉλ©μ λ°λ₯μ λμ¬μ Έ μλ€. μκ·Όμ΄λ μνμ’μ°λ‘λ§ μ΄λν μ μλ€.
μκ·Όμ΄κ° νμΉ μ μλ λ¬Έμμ μ΅λ κ°μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫째 μ€μ ν μ€νΈ μΌμ΄μ€μ κ°μκ° μ£Όμ΄μ§λ€. ν μ€νΈ μΌμ΄μ€μ μλ 100κ°λ₯Ό λμ§ μλλ€.
κ° ν μ€νΈ μΌμ΄μ€μ 첫째 μ€μλ μ§λμ λμ΄μ λλΉ hμ w (2 β€ h, w β€ 100)κ° μ£Όμ΄μ§λ€. λ€μ hκ° μ€μλ λΉλ©μ λνλ΄λ wκ°μ λ¬Έμκ° μ£Όμ΄μ§λ©°, κ° λ¬Έμλ λ€μ μ€ νλμ΄λ€.
- '.'λ λΉ κ³΅κ°μ λνλΈλ€.
- '*'λ λ²½μ λνλ΄λ©°, μκ·Όμ΄λ λ²½μ ν΅κ³Όν μ μλ€.
- '$'λ μκ·Όμ΄κ° νμ³μΌνλ λ¬Έμμ΄λ€.
- μνλ²³ λλ¬Έμλ λ¬Έμ λνλΈλ€.
- μνλ²³ μλ¬Έμλ μ΄μ λ₯Ό λνλ΄λ©°, κ·Έ λ¬Έμμ λλ¬ΈμμΈ λͺ¨λ λ¬Έμ μ΄ μ μλ€.
λ§μ§λ§ μ€μλ μκ·Όμ΄κ° μ΄λ―Έ κ°μ§κ³ μλ μ΄μ κ° κ³΅λ°±μμ΄ μ£Όμ΄μ§λ€. λ§μ½, μ΄μ λ₯Ό νλλ κ°μ§κ³ μμ§ μλ κ²½μ°μλ "0"μ΄ μ£Όμ΄μ§λ€.
μκ·Όμ΄λ μ²μμλ λΉλ©μ λ°μ μμΌλ©°, λΉλ© κ°μ₯μ리μ λ²½μ΄ μλ κ³³μ ν΅ν΄ λΉλ© μνμ λλλ€ μ μλ€. κ°κ°μ λ¬Έμ λν΄μ, κ·Έ λ¬Έμ μ΄ μ μλ μ΄μ μ κ°μλ 0κ°, 1κ°, λλ κ·Έ μ΄μμ΄κ³ , κ°κ°μ μ΄μ μ λν΄μ, κ·Έ μ΄μ λ‘ μ΄ μ μλ λ¬Έμ κ°μλ 0κ°, 1κ°, λλ κ·Έ μ΄μμ΄λ€. μ΄μ λ μ¬λ¬ λ² μ¬μ©ν μ μλ€.
μΆλ ₯
κ° ν μ€νΈ μΌμ΄μ€ λ§λ€, μκ·Όμ΄κ° νμΉ μ μλ λ¬Έμμ μ΅λ κ°μλ₯Ό μΆλ ₯νλ€.
πνμ΄
무μν λ°©λ²μΌλ‘ νμλλ° ν΅κ³Όλλ€..!!
bfsλ‘ λ¬Έμ λ₯Ό νμκ³ , bfsλ₯Ό λ릴 λ μλ‘μ΄ ν€λ₯Ό λ°μλ€λ©΄ κ·Έ κ³³μμ νλ²λ bfsλ₯Ό λλ €μΌνλ€.
λͺ¨λ λ¬Έμμ νλ²μ© λ리면 λλλκ² μλλΌ λ§μ§λ§ λ¬Έμμ μλ‘μ΄ν€λ₯Ό μ»κ³ μ²μ λ¬Έμμ μμν΄μΌ μ΄λ¦¬λ κ΅¬μ‘°κ° μμ μ μμΌλ―λ‘ μ΄μ€forλ¬ΈμΌλ‘ ꡬννλ€.
πμ 체 μ½λ
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <map>
using namespace std;
int _loopCnt = 0, _document = 0;
int _t, _h, _w, cnt = 0;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<vector<char>> _board;
vector<pair<int, int>> _gate;
vector<vector<bool>> _visited;
map<char, bool> _inventory;
bool BFS(int y, int x)
{
bool getKey = false;
if (_board[y][x] >= 'A' && _board[y][x] <= 'Z')
{
// μΈλ²€ν 리 νμΈ.
if (_inventory[_board[y][x] + 32] == true)
_board[y][x] = '.';
else
return false;
}
else if (_board[y][x] >= 'a' && _board[y][x] <= 'z')
{
_inventory[_board[y][x]] = true;
_board[y][x] = '.';
}
else if (_board[y][x] == '$')
{
cnt++;
_board[y][x] = '.';
}
queue<pair<int, int>> q;
q.push({ y, x });
_visited[y][x] = true;
pair<int, int> here;
while (q.empty() == false)
{
here = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int ny = here.first + dy[i];
int nx = here.second + dx[i];
if (ny < 0 || ny >(_h - 1) || nx < 0 || nx >(_w - 1))
continue;
if (_visited[ny][nx])
continue;
if (_board[ny][nx] == '*')
continue;
if (_board[ny][nx] == '.')
{
_visited[ny][nx] = true;
q.push({ ny, nx });
}
else if (_board[ny][nx] >= 'A' && _board[ny][nx] <= 'Z')
{
// μΈλ²€ν 리 νμΈ νμ.
if (_inventory[_board[ny][nx] + 32] == true)
{
_board[ny][nx] = '.';
_visited[ny][nx] = true;
q.push({ ny, nx });
}
}
else if (_board[ny][nx] >= 'a' && _board[ny][nx] <= 'z')
{
_visited[ny][nx] = true;
q.push({ ny, nx });
_inventory[_board[ny][nx]] = true;
_board[ny][nx] = '.';
getKey = true;
}
else if (_board[ny][nx] == '$')
{
_visited[ny][nx] = true;
q.push({ ny, nx });
_board[ny][nx] = '.';
cnt++;
if (cnt == _document)
return false;
}
}
}
_visited.clear();
_visited = vector<vector<bool>>(_h, vector<bool>(_w));
if (getKey == true)
return true;
else
return false;
}
void solve()
{
cin >> _t;
for (int i = 0; i < _t; ++i)
{
cin >> _h >> _w;
cnt = 0;
_board.clear();
_board = vector<vector<char>>(_h, vector<char>(_w));
_visited.clear();
_visited = vector<vector<bool>>(_h, vector<bool>(_w));
_gate.clear();
_inventory.clear();
_loopCnt = 0;
_document = 0;
//_map.clear();
// νλ©΄λ μ
λ ₯
for (int y = 0; y < _h; ++y)
{
string str;
cin >> str;
for (int x = 0; x < _w; ++x)
{
_board[y][x] = str[x];
if ((x == 0 && _board[y][x] != '*') || (y == 0 && _board[y][x] != '*') || (x == _w - 1 && _board[y][x] != '*') || (y == _h - 1 && _board[y][x] != '*'))
_gate.push_back({ y, x });
if (_board[y][x] >= 'A' && _board[y][x] <= 'Z')
_loopCnt++;
if (_board[y][x] == '$')
_document++;
}
}
for (int key = 'a'; key < 'a' + 26; ++key)
{
_inventory[key] = false;
}
// κ°μ§κ³ μλ μ΄μ
string keys;
cin >> keys;
for (int key = 0; key < keys.size(); ++key)
{
_inventory[keys[key]] = true;
}
for (int l = 0; l < _gate.size(); ++l)
{
for (int k = 0; k < _gate.size(); ++k)
{
if (cnt == _document)
break;
if (BFS(_gate[k].first, _gate[k].second) == true)
{
k--;
}
}
}
cout << cnt << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "rt", stdin);
solve();
return 0;
}