백준 9328번 - 열쇠(C++)

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

 

 

문제를 처음 접했을 땐 bfs + bitmasking을 떠올렸다. 왜냐하면 열쇠를 갖고 있는 상태에 따라 이미 visited 되어 있더라도 다시 갈 수도 있기 때문이다. 그러나 이것은 최소거리를 구할 때나 경로를 구할 때나 필요한 것이다. 무슨 말이냐면

 

만약 2, 2 -> 2, 3을 이동하는데 2,3 은 A 열쇠가 없어서 갈 수 없다고 가정하자. 만약 최소거리를 구하는 것이라면 A 열쇠를 찾는 거리까지 고려해야하지만 이 문제는 그냥 도달할 수 있는가 없는가 만을 생각한다.

그래서 2,3이 필요한 열쇠를 다른 곳에 저장해둔다음, 다른 곳에서 탐색했을 때 만약 A 열쇠를 찾는다면 저장해둔 곳을 이제 갈 수 있으므로 큐에 삽입하면 된다.

 

단 문서를 중복으로 도달하는 것을 막기위해 set을 통해 정답을 도출했다. 해본 내용이라고, 익숙하다고 그대로 가지말고 확실하게 문제 의도를 파악하고 알고리즘을 설정하자.

 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
const int key = 27;
const int MAX = 101;
int N, M;
bool visited[MAX][MAX];
bool Key[key];

vector<pair<int, int>> readyQueue[27];
vector<pair<int, int>> startingGrid;

char board[MAX][MAX];

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

set<pair<int, int>> answer;

bool range(int x, int y){
	return x > -1 && x < N && y > -1 && y < M;
}

void bfs(){
	queue<pair<int, int>> q;
	for(pair<int, int> s : startingGrid){
		q.push({s.first, s.second});
		visited[s.first][s.second] = true;
	}

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

		visited[x][y] = true;

		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(range(nx, ny) && !visited[nx][ny] && board[nx][ny] != '*'){
				visited[nx][ny] = true;

				if(board[nx][ny] <= 'Z' && board[nx][ny] >= 'A'){
					//cout << board[nx][ny] << " " << Key[board[nx][ny] - 'A' + 1] << endl;
					if(Key[board[nx][ny] - 'A' + 1]){
						q.push({nx, ny});
					}else{
						readyQueue[board[nx][ny] - 'A' + 1].push_back({nx, ny});
					}
				}else if(board[nx][ny] <= 'z' && board[nx][ny] >= 'a'){
					Key[board[nx][ny] - 'a' + 1] = true;
					q.push({nx, ny});

					for(pair<int, int> s : readyQueue[board[nx][ny] - 'a' + 1]){
						q.push({s.first, s.second});
						visited[s.first][s.second] = true;
					}		
				}
				else if(board[nx][ny] == '$'){
					answer.insert({nx, ny});
					q.push({nx, ny});
				}else{
					q.push({nx, ny});
				}
			}
		}
	}
}

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
	vector<int> answerList;
	int T; cin >> T;

	for(int t = 0; t < T; t++){
		cin >> N >> M;

		for(int i = 0; i < 27; i++){
			readyQueue[i].clear();
		}
		startingGrid.clear();
		answer.clear();

		memset(visited, false, sizeof visited);
		memset(Key, false, sizeof Key);

		for(int i = 0; i < N; i++){
			string tmp; cin >> tmp;
			for(int j = 0; j < M; j++){
				board[i][j] = tmp[j];

				if(i == 0 || i == N - 1 || j == 0 || j == M - 1){
					if(board[i][j] <= 'Z' && board[i][j] >= 'A'){
						readyQueue[board[i][j] - 'A' + 1].push_back({i, j});
					}
				}
			}
		}

		string firstKey;

		cin >> firstKey;
		if(firstKey != "0"){
			for(char k : firstKey){
				Key[k - 'a' + 1] = true;

				for(pair<int, int> p : readyQueue[k - 'a' + 1]){
					startingGrid.push_back({p.first, p.second});
				}
			}
		}

		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(i == 0 || i == N - 1 || j == 0 || j == M - 1){
					if(board[i][j] != '*'){
						if(board[i][j] <= 'z' && board[i][j] >= 'a'){
							startingGrid.push_back({i, j});
							Key[board[i][j] - 'a' + 1] = true;

							for(pair<int, int> p : readyQueue[board[i][j] - 'a' + 1]){
								startingGrid.push_back({p.first, p.second});
							}
						}else if(board[i][j] == '.'){
							startingGrid.push_back({i, j});
						}else if(board[i][j] == '$'){
							answer.insert({i, j});
							startingGrid.push_back({i, j});
						}
					}
				}
			}
		}

		bfs();

		answerList.push_back(answer.size());
	}

	for(int ans : answerList){
		cout << ans << '\n';
	}
}