[백준 9328] 열쇠 (C++)

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

문제

---

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

 

출력

---

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

문제 풀이

---

bfs 문제.

 

빌딩의 테두리에서만 진입할 수 있고, 여러개의 루트 중 하나만 선택해서 가져오는 것이 아니라 다른 입구를 이용해 여러 번 침입하여 최대한 문서를 많이 가져와야 한다.

열쇠를 얻었을 때 열 수 있는 문들을 알 수 있도록 26칸짜리 벡터 배열을 선언하여 각 알파벳에 해당하는 인덱스의 벡터에 문의 위치를 저장해둔다.

 

테두리 중 빈 공간, 문서가 있는 곳, 열쇠가 있는 곳, 가진 열쇠로 열 수 있는 문은 침입 가능하므로 큐에 넣어준다. 열쇠를 획득했을 때, 이전에 그와 대응하는 문이 있는 곳에 도달했지만 열쇠가 없어 이동할 수 없었던 곳에 진입이 가능해진다. 따라서 이전에 방문했지만 열쇠가 없어 열지 못했던 곳들을 저장하는 26칸짜리 벡터 배열도 하나 만들어둔다. 그리고 열쇠가 없어 열지 못한다면 해당 배열에 저장해두고, 이후 이와 대응하는 열쇠를 얻었을 때 이 배열의 정보를 읽어와 큐에 넣어주도록 한다. 또한 해당 열쇠와 대응되는 문이지만 아직 방문하지 않은 곳은 이동 가능하므로 지도에 해당 위치를 .로 표시하도록 한다.

 

모든 테두리를 탐색하여 침입 가능한  위치를 큐에 넣어두었다면 bfs 탐색을 통해 빌딩의 이동 가능한 위치들을 모두 탐색한다.

탐색하며 나타날 수 있는 경우의 수는 다음과 같다.

1. 열쇠가 있는 곳: 이미 획득한 열쇠라면 방문 처리하고 큐에 넣어주면 된다. 새 열쇠라면 테두리 때와 같이 대응하는 문 중 이미 방문한 곳의 위치를 얻어와 큐에 넣는 작업과 아직 방문하지 않은 곳은 편의를 위해 빈 공간으로 변경하는 작업도 함께 해준다.

2. 빈 공간: 기본 bfs와 같이 방문처리하고 큐에 넣는다.

3. 문서가 있는 곳: 위와 마찬가지. 얻을 수 있는 문서의 개수를 1증가 시켜주면 된다.

4. 문이 있는 곳: 1에 의해 아직 방문하지 않은 곳은 빈 공간으로 변경되었으므로 해당 문은 아직 열쇠가 없어 열지 못하는 문이다. 방문 처리하고 방문하였으나 아직 열지 못하는 문의 위치를 저장하는 벡터 배열에 해당 문의 위치를 저장해준다. 이후 탐색하며 대응하는 열쇠를 만나면 1에 의해 이 문이 위치하는 곳에서의 탐색을 계속할 수 있다.

5. 벽이 있는 곳 / 이미 방문한 곳: 진입하지 못하거나 또 방문할 필요가 없으므로 처리할 필요가 없다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <set>
using namespace std;
int N, M;
string keyStr;
char** map;
bool** isVisited;
vector<pair<int, int>>* doorPos;
vector<pair<int, int>>* visitedDoorButCanNotOpen;
set<char> keys;

queue<pair<int, int>> bfsQueue;
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };

int answer = 0;

void openDoor(char c)
{
	int index = c - 97;
	for (int j = 0; j < doorPos[index].size(); j++)
	{
		int doorPosX = doorPos[index].at(j).first;
		int doorPosY = doorPos[index].at(j).second;
		map[doorPosX][doorPosY] = '.';
	}
	for (int j = 0; j < visitedDoorButCanNotOpen[index].size(); j++) // 방문했지만 열지 못하는 문에 다시 방문.
	{
		int doorPosX = visitedDoorButCanNotOpen[index].at(j).first;
		int doorPosY = visitedDoorButCanNotOpen[index].at(j).second;
		bfsQueue.push(pair(doorPosX, doorPosY));
	}
	visitedDoorButCanNotOpen[index].clear();
}

void pushToQueue(int xPos, int yPos)
{
	isVisited[xPos][yPos] = true;
	if (map[xPos][yPos] == '$')
	{
		answer++;
	}
	bfsQueue.push(pair(xPos, yPos));
}

void bfs()
{
	while (!bfsQueue.empty())
	{
		pair<int, int> current = bfsQueue.front();
		for (int i = 0; i < 4; i++)
		{
			int nextX = current.first + dx[i];
			int nextY = current.second + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY] == false && map[nextX][nextY] == '$')
			{
				answer++;
				isVisited[nextX][nextY] = true;
				bfsQueue.push(pair(nextX, nextY));
			}
			else if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY] == false && map[nextX][nextY] == '.')
			{
				isVisited[nextX][nextY] = true;
				bfsQueue.push(pair(nextX, nextY));
			}
			else if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY] == false && map[nextX][nextY] >= 97) //열쇠가 있는 곳 방문
			{
				bfsQueue.push(pair(nextX, nextY));
				isVisited[nextX][nextY] = true;
				if (keys.find(map[nextX][nextY]) == keys.end()) // 새 열쇠
				{
					keys.insert(map[nextX][nextY]);
					int index = map[nextX][nextY] - 97;
					for (int j = 0; j < visitedDoorButCanNotOpen[index].size(); j++) // 방문했지만 열지 못하는 문에 다시 방문.
					{
						int doorPosX = visitedDoorButCanNotOpen[index].at(j).first;
						int doorPosY = visitedDoorButCanNotOpen[index].at(j).second;
						bfsQueue.push(pair(doorPosX, doorPosY));
					}
					visitedDoorButCanNotOpen[index].clear();
					for (int j = 0; j < doorPos[index].size(); j++)
					{
						int doorPosX = doorPos[index].at(j).first;
						int doorPosY = doorPos[index].at(j).second;
						map[doorPosX][doorPosY] = '.';
					}
				}
			}
			else if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY] == false && map[nextX][nextY] >= 65 && map[nextX][nextY] < 97) //아직 열지 못하는 문
			{
				isVisited[nextX][nextY] = true;
				int index = map[nextX][nextY] + 32 - 97;
				visitedDoorButCanNotOpen[index].push_back(pair(nextX, nextY));
			}
		}
		bfsQueue.pop();
	}
}

void reset()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			isVisited[i][j] = false;
		}
	}
}

void findStartPointSero(int yPos)
{
	for (int i = 0; i < N; i++)
	{
		if (isVisited[i][yPos] == false)
		{
			if (map[i][yPos] == '.' || map[i][yPos] == '$')
			{
				pushToQueue(i, yPos);
			}
			else if (map[i][yPos] >= 97)
			{
				openDoor(map[i][yPos]);
				pushToQueue(i, yPos);
			}
			else if (map[i][yPos] >= 65 && map[i][yPos] < 97)
			{
				isVisited[i][yPos] = true;
				int index = map[i][yPos] + 32 - 97;
				visitedDoorButCanNotOpen[index].push_back(pair(i, yPos));
			}
		}
	}
}

void findStartPointGaro(int xPos)
{
	for (int j = 0; j < M; j++)
	{
		if (isVisited[xPos][j] == false)
		{
			if (map[xPos][j] == '.' || map[xPos][j] == '$')
			{
				pushToQueue(xPos, j);
			}
			else if (map[xPos][j] >= 97)
			{
				openDoor(map[xPos][j]);
				pushToQueue(xPos, j);
			}
			else if (map[xPos][j] >= 65 && map[xPos][j] < 97)
			{
				isVisited[xPos][j] = true;
				int index = map[xPos][j] + 32 - 97;
				visitedDoorButCanNotOpen[index].push_back(pair(xPos, j));
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		keys.clear();
		answer = 0;
		cin >> N >> M;
		map = new char* [N];
		isVisited = new bool* [N];
		doorPos = new vector<pair<int, int>>[26];
		visitedDoorButCanNotOpen = new vector<pair<int, int>>[26];
		for (int i = 0; i < N; i++)
		{
			map[i] = new char[M];
			isVisited[i] = new bool[M];
			for (int j = 0; j < M; j++)
			{
				isVisited[i][j] = false;
				cin >> map[i][j];
				if (map[i][j] >= 65 && map[i][j] < 97)
				{
					int index = map[i][j] - 65;
					doorPos[index].push_back(pair(i, j));
				}
			}
		}
		cin >> keyStr;
		if (keyStr == "0")
		{
			keyStr = "";
		}
		for (int i = 0; i < keyStr.size(); i++)
		{
			keys.insert(keyStr.at(i));
			openDoor(keyStr.at(i));
		}
		findStartPointSero(0);
		findStartPointSero(M - 1);
		findStartPointGaro(0);
		findStartPointGaro(N - 1);
		bfs();
		cout << answer << "\n";
	}
	return 0;
}