BOJ 9328 - 열쇠

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	9130	2446	1530	24.186%

문제

---

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

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

입력

---

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

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

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

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

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

출력

---

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

접근

---

외곽에서 들어갈 수 있는 행렬같은 경우는 padding 값을 주면 편하다.
패딩이 없다면? 아주 귀찮은 예외처리 코드가 필요할 것이다.

열쇠는 최대 26개이므로, 비트마스크로 관리할 수 있다.
{0, 0}에서 출발하는데, 열쇠를 주울때마다 visited 배열을 초기화 해주면
빠지는 경우 없이 모든 상황을 순회할 수 있다.
한번 들린 문서, 열쇠, 문들은 '.'으로 바꿔주면 더 편하다.

풀이

---

코드가 길어질 것 같아 비트연산을 위한 여러 함수를 만들었다.
K값을 통해 key들을 관리해주었다.
자세한 구현은 주석을 통해 확인할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int T, N, M;
string key;
bool visited[102][102];
char arr[102][102];

bool isKey(char ch)
{
	if (ch >= 'a' && ch <= 'z') return true;
	else return false;
}

bool isDoor(char ch)
{
	if (ch >= 'A' && ch <= 'Z') return true;
	else return false;
}

int small(char ch)
{
	return 1 << (ch - 'a');
}

int big(char ch)
{
	return 1 << (ch - 'A');
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN(T);
	while (T--)
	{
		int cnt = 0;
		int K = 0; // 가지고 있는 열쇠 저장
		CIN2(N, M);
		FUP(i, 1, N)
		{
			FUP(j, 1, M)
			{
				CIN(arr[i][j]);
			}
		}
		CIN(key);
		if (key != "0")
		{
			for (char ch : key)
			{
				K |= small(ch); // 비트 연산으로 열쇠 추가
			}
		}

		// '.'으로 패딩 씌우기
		FUP(i, 0, N + 1)
		{
			for (int j : {0, M + 1})
			{
				arr[i][j] = '.';
			}
		}
		for (int i : {0, N + 1})
		{
			FUP(j, 0, M + 1)
			{
				arr[i][j] = '.';
			}
		}
		queue<pair<int, int>> q;
		MS(visited, false);
		visited[0][0] = true;
		q.push({ 0, 0 });
		while (!q.empty())
		{
			int y = q.front().first;
			int x = q.front().second;
			if (arr[y][x] == '$') // 문서면 가져오고 '.'으로 바꾸기
			{
				cnt++;
				arr[y][x] = '.';
			}
			q.pop();
			if (!visited[y][x]) continue; // key를 주워서 초기화됐으면, 넘김
			FUP(i, 0, 3)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny > N + 1 || nx > M + 1 || arr[ny][nx] == '*' || visited[ny][nx]) continue;
				if (isKey(arr[ny][nx]))
				{
					if ((K | small(arr[ny][nx])) - K != 0) // 없는 키일때,
					{
						MS(visited, false); // visited 배열 초기화 후 다시 순회
						K |= small(arr[ny][nx]); // 열쇠 추가
					}
					visited[ny][nx] = true;
					arr[ny][nx] = '.'; // 주웠으면 '.'으로 바꾸기
					q.push({ ny, nx });
				}
				else if (isDoor(arr[ny][nx]))
				{
					if ((K & big(arr[ny][nx])) == 0) continue; // K에 없으면 못들어간다
					arr[ny][nx] = '.';
					visited[ny][nx] = true;
					q.push({ ny, nx });
				}
				else
				{
					visited[ny][nx] = true;
					q.push({ ny, nx });
				}
			}
		}
		COUT(cnt);
		ENDL;
	}

	return 0;
}