[백준] 9328 열쇠
문제
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
- '.'는 빈 공간을 나타낸다.
- '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- '$'는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
골드1 문제입니다.
1. 상근이는 빌딩 밖에있고, 열려있는 문 어디로든 들어갈 수 있습니다.
주어진배열 상하좌우로 한칸씩 마진을 '.'(빈칸)으로 두어, 0,0에서 그래프 탐색을 시작하면 어디로든지 들어갈 수 있게
2. 논리는 다음과 같습니다.
상근이가 0,0에서 출발해서 이동할 수 있는칸까지 이동합니다. 이동중에 열쇠를 하나라도 얻었다면, 0,0에서 다시 출발 할것입니다. 얻은 열쇠를 이용해 문을 열면서 이동합니다.
만약 상근이가 더이상 얻을 수있는 열쇠가 없어 더이상 문을 열수 없다면 , 마지막으로 0,0에서 출발합니다.
0,0에서 출발하여 $를 만나면 문서의 수를 더합니다.
3.각칸의 격자에서 이동하는 비용은 일정하고, 모든 길을 탐색하므로 그래프탐색 BFS를 사용합니다.
4. 소지하고 있는 열쇠와, 획득한 열쇠들은 비트마스크로 표시했습니다.
#include<bits/stdc++.h>
using namespace std;
int keys = 0, dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
char mp[102][102];
bool visited[102][102], getKey;
vector<int>answer;
vector<pair<int, int>>temp;
void initmap() { //매번 케이스별 초기화
temp.clear();
for (int i = 0; i < 102; i++) {
for (int j = 0; j < 102; j++)
mp[i][j] = '.';
}
doors = 0;
keys = 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t, n, m, ans;
cin >> t;
while (t--) {
initmap();
cin >> n >> m;
ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
}
}
string str;
cin >> str;
if (str != "0")
for (int i = 0; i < str.length(); i++) {
keys |= (1 << (str[i] - 'a')); //비트마스크 0~26개의 알파벳 저장
}
while (1) {
getKey = false; //bfs를 반복해서 돌면서 열쇠를 더이상 얻을 수 없을때 까지
memset(visited, 0, sizeof(visited));
queue<pair<int, int>>q;
q.push({ 0,0 });
visited[0][0] = 1;
while (!q.empty()) {
auto [y, x] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && ny < n + 2 && nx >= 0 && nx < m + 2) { //범위 내
if (!visited[ny][nx] && mp[ny][nx] != '*') { //미방문, 벽이아닌지역
if ('a' <= mp[ny][nx] && mp[ny][nx] <= 'z') { //지금껏 얻지 못한 열쇠를 얻으면
keys |= (1 << (mp[ny][nx] - 'a')); //열쇠획득시 저장
mp[ny][nx] = '.'; //빈칸이됨
getKey = true; //이번차례에는 열쇠를 얻음
}
else if ('A' <= mp[ny][nx] && mp[ny][nx] <= 'Z') { //문을 만나면
if (!(keys & (1 << mp[ny][nx] - 'A'))) {
continue;
//보유한 열쇠 없으면 continue;
}
else {
mp[ny][nx] = '.';//문이 열림. 빈칸이 됨.
}
}
visited[ny][nx] = 1; //방문처리
q.push({ ny,nx });
}
}
}
}
if (!getKey) {//열쇠를 얻지못함, 즉 세면 됨
memset(visited, 0, sizeof(visited));
queue<pair<int, int>>q;
q.push({ 0,0 });
visited[0][0] = 1;
while (!q.empty()) {
auto [y, x] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && ny < n + 2 && nx >= 0 && nx < m + 2) {
if (!visited[ny][nx] && mp[ny][nx] != '*') {
if (mp[ny][nx] == '$')
ans++;
else if ('A' <= mp[ny][nx] && mp[ny][nx] <= 'Z') {
continue;
}
visited[ny][nx] = 1;
q.push({ ny,nx });
}
}
}
}
answer.push_back(ans);
break;
}
}
}
for (auto r : answer)
cout << r << "\n";
}
이 문제를 풀면서 중요한 점은 다음과 같습니다.
1. 가장자리에 1칸씩 마진을 둘 수 있는가.
2. 열쇠를 얻으면서 열수있는 모든 문을 모두 열 때까지 어떻게 진행할지.