백준 9328 열쇠 (c++) : 피너클

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

9328번: 열쇠

복잡한 bfs문제다.

int h, w;
bool can[27], visited[101][101];
string map[101];
string s;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

can은 가지고 있는 열쇠, visited는 현재까지 방문한 공간,

map은 빌딩의 평면도, s는 처음 주어지는 열쇠다.

int test;
cin >> test;
while (test-- > 0) {
	cin >> h >> w;
	for (int i = 0; i < h; i++) cin >> map[i];
	cin >> s;
	memset(can, false, sizeof(can));
	if (s[0] != '0') for (int i = 0; i < s.length(); i++) can[s[i] - 'a'] = true;
	cout << bfs() << endl;
}

테스트케이스 수를 입력받고 그만큼 반복문을 돌린다.

h, w를 입력받고 map을 입력받은다음 s를 입력받는다.

만약 s가 "0"이 아니라면 열쇠를 가지고 있다는 뜻이다. can[s[i]-'a']를 이용해 가지고 있는 열쇠에 추가한다.

만약 s[i]가 'a' 라면 'a'-'a'=0이니 can[0] = true가 될것이다.

그후 bfs를 실행시켜 출력한다.

int bfs() {
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	vector<pair<int, int>> v;
	int ans = 0;

visited를 초기화 시키도 queue와 vector를 선언한다.

queue에는 지나갈 공간의 좌표가 주어지고 vector에는 열지못한 문의 좌표가 주어진다.

int ans는 얻은 문서의 숫자다.

 

상근이는 빌딩의 가장자리로 침입할수있다. 그러니 미리 가장자리에서 들어갈수있는 자리를 모두 q에 넣어준다.

만약 현재 공간이 '.'이라면 q에 넣는다.

만약 현재 공간이 알파벳 소문자라면 q에 넣고 can을 업데이트한다.

만약 현재 공간이 알파벳 대문자라면 두가지고 나뉜다.

열쇠를 가지고 있는경우 q에 넣지만 열쇠를 가지고 있지 않다면 v에 넣는다.

만약 현재 공간이 '$'라면 q에 넣고 ans + 1을 해준다.

이 모든 과정을 모든 가로, 세로 가장자리 부분에 실행하면 된다.

for (int i = 0; i < w; i++) {
		if (map[0][i] == '.') q.push({ 0, i }), visited[0][i] = true;
		else if ('a' <= map[0][i] && map[0][i] <= 'z') {
			q.push({ 0, i }), visited[0][i] = true;
			can[map[0][i] - 'a'] = true;
		}
		else if ('A' <= map[0][i] && map[0][i] <= 'Z') {
			if (can[map[0][i] - 'A']) {
				q.push({ 0, i }), visited[0][i] = true;
			}
			else v.push_back({ 0, i });
		}
		else if (map[0][i] == '$') {
			q.push({ 0, i }), visited[0][i] = true;
			ans++;
		}

		if (map[h - 1][i] == '.')q.push({ h - 1, i }), visited[h - 1][i] = true;
		else if ('a' <= map[h - 1][i] && map[h - 1][i] <= 'z') {
			q.push({ h - 1, i }), visited[h - 1][i] = true;
			can[map[h - 1][i] - 'a'] = true;
		}
		else if ('A' <= map[h - 1][i] && map[h - 1][i] <= 'Z') {
			if (can[map[h - 1][i] - 'A']) {
				q.push({ h - 1, i }), visited[h - 1][i] = true;
			}
			else v.push_back({ h - 1, i });
		}
		else if (map[h - 1][i] == '$') {
			q.push({ h - 1, i }), visited[h - 1][i] = true;
			ans++;
		}
	}
	for (int i = 1; i < h - 1; i++) {
		if (map[i][0] == '.') q.push({ i, 0 }), visited[i][0] = true;
		else if ('a' <= map[i][0] && map[i][0] <= 'z') {
			q.push({ i, 0 }), visited[i][0] = true;
			can[map[i][0] - 'a'] = true;
		}
		else if ('A' <= map[i][0] && map[i][0] <= 'Z') {
			if (can[map[i][0] - 'A']) {
				q.push({ i, 0 }), visited[i][0] = true;
			}
			else v.push_back({ i, 0 });
		}
		else if (map[i][0] == '$') {
			q.push({ i, 0 }), visited[i][0] = true;
			ans++;
		}

		if (map[i][w - 1] == '.')q.push({ i, w - 1 }), visited[i][w - 1] = true;
		else if ('a' <= map[i][w - 1] && map[i][w - 1] <= 'z') {
			q.push({ i, w - 1 }), visited[i][w - 1] = true;
			can[map[i][w - 1] - 'a'] = true;
		}
		else if ('A' <= map[i][w - 1] && map[i][w - 1] <= 'Z') {
			if (can[map[i][w - 1] - 'A']) {
				q.push({ i, w - 1 }), visited[i][w - 1] = true;
			}
			else v.push_back({ i, w - 1 });
		}
		else if (map[i][w - 1] == '$') {
			q.push({ i, w - 1 }), visited[i][w - 1] = true;
			ans++;
		}
	}

그후 bfs알고리즘을 만든다.

while (!q.empty()) {
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	visited[y][x] = true;

기본 세팅을 하고

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= ny && ny < h && 0 <= nx && nx < w) {
			if (!visited[ny][nx]) {

현재 좌표에서 갈수있는 다음 좌표인 ny와 nx를 선언한다.

그후 ny와 nx가 범위안에 있고 아직 방문하지 않은 공간이라면

				if (map[ny][nx] == '.') {
					q.push({ ny, nx });
					visited[ny][nx] = true;
				}
				else if ('a' <= map[ny][nx] && map[ny][nx] <= 'z') {
					q.push({ ny, nx });
					visited[ny][nx] = true;
					can[map[ny][nx] - 'a'] = true;
				}
				else if ('A' <= map[ny][nx] && map[ny][nx] <= 'Z') {
					if (can[map[ny][nx] - 'A']) {
						q.push({ ny, nx });
						visited[ny][nx] = true;
					}
					else {
						v.push_back({ ny, nx });
					}
				}
				else if (map[ny][nx] == '$') {
					q.push({ ny, nx });
					visited[ny][nx] = true;
					ans++;
				}

가장자리를 검사한것와 똑같은 검사를 해준다.

	if (q.empty()) {
		for (int i = 0; i < v.size(); i++) {
			if (can[map[v[i].first][v[i].second] - 'A'] && !visited[v[i].first][v[i].second]) {
				q.push({ v[i].first, v[i].second });
				visited[v[i].first][v[i].second] = true;
			}
		}
	}

만약 위의 검사를 모두 실행했는데 q가 빈 상태가 됬다면 아직 열지 못한 문들을 조사한다.

v 전체를 검사하며 열쇠를 가지고 있고 아직 방문하지 않은 공간이라면 q에 넣는다.

	}
	return ans;
}

마지막으로 ans를 리턴한다.

#include <iostream>
#include <string>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

int h, w;
bool can[27], visited[101][101];
string map[101];
string s;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

int bfs() {
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	vector<pair<int, int>> v;
	int ans = 0;

	for (int i = 0; i < w; i++) {
		if (map[0][i] == '.') q.push({ 0, i }), visited[0][i] = true;
		else if ('a' <= map[0][i] && map[0][i] <= 'z') {
			q.push({ 0, i }), visited[0][i] = true;
			can[map[0][i] - 'a'] = true;
		}
		else if ('A' <= map[0][i] && map[0][i] <= 'Z') {
			if (can[map[0][i] - 'A']) {
				q.push({ 0, i }), visited[0][i] = true;
			}
			else v.push_back({ 0, i });
		}
		else if (map[0][i] == '$') {
			q.push({ 0, i }), visited[0][i] = true;
			ans++;
		}

		if (map[h - 1][i] == '.')q.push({ h - 1, i }), visited[h - 1][i] = true;
		else if ('a' <= map[h - 1][i] && map[h - 1][i] <= 'z') {
			q.push({ h - 1, i }), visited[h - 1][i] = true;
			can[map[h - 1][i] - 'a'] = true;
		}
		else if ('A' <= map[h - 1][i] && map[h - 1][i] <= 'Z') {
			if (can[map[h - 1][i] - 'A']) {
				q.push({ h - 1, i }), visited[h - 1][i] = true;
			}
			else v.push_back({ h - 1, i });
		}
		else if (map[h - 1][i] == '$') {
			q.push({ h - 1, i }), visited[h - 1][i] = true;
			ans++;
		}
	}
	for (int i = 1; i < h - 1; i++) {
		if (map[i][0] == '.') q.push({ i, 0 }), visited[i][0] = true;
		else if ('a' <= map[i][0] && map[i][0] <= 'z') {
			q.push({ i, 0 }), visited[i][0] = true;
			can[map[i][0] - 'a'] = true;
		}
		else if ('A' <= map[i][0] && map[i][0] <= 'Z') {
			if (can[map[i][0] - 'A']) {
				q.push({ i, 0 }), visited[i][0] = true;
			}
			else v.push_back({ i, 0 });
		}
		else if (map[i][0] == '$') {
			q.push({ i, 0 }), visited[i][0] = true;
			ans++;
		}

		if (map[i][w - 1] == '.')q.push({ i, w - 1 }), visited[i][w - 1] = true;
		else if ('a' <= map[i][w - 1] && map[i][w - 1] <= 'z') {
			q.push({ i, w - 1 }), visited[i][w - 1] = true;
			can[map[i][w - 1] - 'a'] = true;
		}
		else if ('A' <= map[i][w - 1] && map[i][w - 1] <= 'Z') {
			if (can[map[i][w - 1] - 'A']) {
				q.push({ i, w - 1 }), visited[i][w - 1] = true;
			}
			else v.push_back({ i, w - 1 });
		}
		else if (map[i][w - 1] == '$') {
			q.push({ i, w - 1 }), visited[i][w - 1] = true;
			ans++;
		}
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		visited[y][x] = true;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0 <= ny && ny < h && 0 <= nx && nx < w) {
				if (!visited[ny][nx]) {
					if (map[ny][nx] == '.') {
						q.push({ ny, nx });
						visited[ny][nx] = true;
					}
					else if ('a' <= map[ny][nx] && map[ny][nx] <= 'z') {
						q.push({ ny, nx });
						visited[ny][nx] = true;
						can[map[ny][nx] - 'a'] = true;
					}
					else if ('A' <= map[ny][nx] && map[ny][nx] <= 'Z') {
						if (can[map[ny][nx] - 'A']) {
							q.push({ ny, nx });
							visited[ny][nx] = true;
						}
						else {
							v.push_back({ ny, nx });
						}
					}
					else if (map[ny][nx] == '$') {
						q.push({ ny, nx });
						visited[ny][nx] = true;
						ans++;
					}
				}
			}
		}
		if (q.empty()) {
			for (int i = 0; i < v.size(); i++) {
				if (can[map[v[i].first][v[i].second] - 'A'] && !visited[v[i].first][v[i].second]) {
					q.push({ v[i].first, v[i].second });
					visited[v[i].first][v[i].second] = true;
				}
			}
		}
	}
	return ans;
}

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

	int test;
	cin >> test;
	while (test-- > 0) {
		cin >> h >> w;
		for (int i = 0; i < h; i++) cin >> map[i];
		cin >> s;
		memset(can, false, sizeof(can));
		if (s[0] != '0') for (int i = 0; i < s.length(); i++) can[s[i] - 'a'] = true;
		cout << bfs() << endl;
	}
}

전체코드다.