[PS] 열쇠 / C++ (백준 9328번)

 

그래프 탐색에 대한 이해도만 있으면 쉽게 풀 수 있는 문제

대게 bfs로 풀었던데 귀찮아서 dfs로 풀었다.

각 열쇠마다 열지 못한 문의 좌표를 저장하는 벡터를 만든 다음, 새로운 열쇠가 나왔을 때 벡터에 저장되어 있는 열지 못했던 문을 다시 탐색하는 방식으로 구현하여  풀었다.

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include <cctype>
#include<vector>
using namespace std;

char d[101][101];
bool vi[101][101], key[27];
int doc = 0, x_size, y_size;
vector < pair<int, int> > blocked[27];

int f(int x, int y) {
	if (d[y][x] == '*')return 0;
	else if (d[y][x] == '$')doc++;
	else if (d[y][x] != '.') {
		if (isupper(d[y][x])) {
			if (key[d[y][x] - 'A'] == false) {
				blocked[d[y][x] - 'A'].push_back(make_pair(y, x));
				vi[y][x] = 0;
				return 0;
			}
		}
		else {
			if (key[d[y][x] - 'a'] == false) {
				key[d[y][x] - 'a'] = true;
				int vec_size = blocked[d[y][x] - 'a'].size();
				for (int i = 0; i < vec_size; i++) {
					pair<int, int> pa = blocked[d[y][x] - 'a'][i];
					if (vi[pa.first][pa.second] == true)continue;
					vi[pa.first][pa.second] = true;
					f(pa.second, pa.first);
				}
				blocked[d[y][x] - 'a'].clear();
			}
		}
	}

	if (x > 0 && vi[y][x - 1] == false) {
		vi[y][x - 1] = true;
		f(x - 1, y);
	}
	if (y > 0 && vi[y - 1][x] == false) {
		vi[y - 1][x] = true;
		f(x, y - 1);
	}
	if (x < x_size - 1 && vi[y][x + 1] == false) {
		vi[y][x + 1] = true;
		f(x + 1, y);
	}
	if (y < y_size - 1 && vi[y + 1][x] == false) {
		vi[y + 1][x] = true;
		f(x, y + 1);
	}
	return 0;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int t = 0; t < n; t++) {
		string str;
		scanf("%d %d", &y_size, &x_size);
		for (int i = 0; i < y_size; i++) {
			scanf("%s", d[i]);
		}
		cin >> str;
		for (int i = 0; i < str.length(); i++) {
			if(str[i] == '0')continue;
			key[str[i] - 'a'] = true;
		}

		for (int i = 0; i < x_size; i++) {
			if (vi[0][i] == 0) {
				vi[0][i] = 1;
				f(i, 0);
			}
			if (vi[y_size - 1][i] == 0) {
				vi[y_size - 1][i] = 1;
				f(i, y_size - 1);
			}
		}

		for (int i = 1; i < y_size - 1; i++) {
			if (vi[i][0] == 0) {
				vi[i][0] = 1;
				f(0, i);
			}
			if (vi[i][x_size - 1] == 0) {
				vi[i][x_size - 1] = 1;
				f(x_size - 1, i);
			}
		}

		printf("%d\n", doc);

		memset(d, 0, sizeof(d));
		memset(vi, 0, sizeof(vi));
		memset(key, 0, sizeof(key));
		for (int i = 0; i < 27; i++)blocked[i].clear();
		doc = 0;
	}
	return 0;
}