백준 9328 - 열쇠(C++, 복습)

문제 링크입니다. https://www.acmicpc.net/problem/9328

9328번: 열쇠

BFS를 이용한 문제입니다.

문서를 얼마나 훔칠 수 있는지 구하는 문제입니다.

자신이 가지고 있던 열쇠와 얻은 열쇠를 통해 닫힌 문을 열 수 있기에 복잡했던 문제입니다.

 

먼저 상근이는 map의 바깥에서 접근할 수 있습니다. 

그렇기에 이전에 저장했던 map 값이 다음 탐색에도 영향을 줄 수 있기에 이를 막아줘야합니다.

1. map을 모두 초기화하기

2. map의 주변에 일정한 값으로 저장해주기

2개중 한가지 방법을 이용해 이전의 값이 현재 탐색에 영향을 주지 못하도록 해줍니다.

 

그 다음은 key를 저장하는 방법입니다.

열쇠는 a~z까지 총 26개가 있습니다. 따라서 배열을 이용해 ['a' - 'a' + 1] 과 같은 방법으로 열쇠 유무를 저장했습니다.

 

 

BFS를 통해 탐색할 때, 탐색하지 못하는 경우는 2가지입니다.

1. 벽에 막힌경우

2. 문에 막힌경우

 

여기에서 벽에 막힌 경우는 아예 가지 못하기에 신경 쓸 필요가 없습니다.

하지만, 문에 막힌 경우는 다릅니다. 여기는 나중에 해당 문을 열 수 있는 열쇠를 얻을 경우 해당 위치부터 다시 탐색을 할 수 있기에 해당 좌표를 저장해줘야합니다.

따라서, 저는 door라는 queue를 배열로 만들어, A~Z 벽에 도달했는데, 문을 열지 못하는 경우에 door에 저장해줬습니다.

 

door를 통해 저장했다면, 탐색 중에 열쇠를 얻었을 경우, 해당 열쇠로 열 수 있는 문들이 door queue에 저장되어 있으니까 해당 좌표들을 전부 탐색할 수 있도록 해줬습니다. door 큐도 똑같이 26칸을 만들어 알파벳 순서대로 저장했습니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define LL long long

using namespace std;

int test_case, W, H;
char map[110][110];
int check[110][110];
int key[27]; // a~z
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int ans;


void bfs(int X, int Y){
	queue<P> q;	
	queue<P> door[27];  // A~Z
	check[X][Y] = 1;
	q.push({X,Y});
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 0 && xx <= H + 1 && yy >= 0 && yy <= W + 1){
				if(check[xx][yy] != 0 || map[xx][yy] == '*') continue;
				check[xx][yy] = 1;
				if(map[xx][yy] >= 'A' && map[xx][yy] <= 'Z'){
					if(key[map[xx][yy] - 'A' + 1] == 1){
						q.push({xx,yy});
					}
					else{
						door[map[xx][yy] - 'A' + 1].push({xx,yy});
					}
				}
				else if(map[xx][yy] >= 'a' && map[xx][yy] <= 'z'){
				    q.push({xx, yy});
					if(key[map[xx][yy] - 'a' + 1] == 0){
						key[map[xx][yy] - 'a' + 1] = 1;
						while(!door[map[xx][yy] - 'a' + 1].empty()){
							q.push(door[map[xx][yy] - 'a' + 1].front());
							door[map[xx][yy] - 'a' + 1].pop();
						}
					}
				}
				else{
					if(map[xx][yy] == '$') ans++;
					q.push({xx,yy});
				}
			}
		}
	}
}

void solve(){
	bfs(0,0);		
	cout << ans << "\n";
	ans = 0;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int k = 0; k < test_case; k++){
		memset(key,0,sizeof(key));
		memset(check,0,sizeof(check));
		cin >> H >> W;
		for(int i = 1; i <= H; i++){
			for(int j = 1; j <= W; j++){
				cin >> map[i][j];
			}
		}
		for(int i = 0; i <= H+1; i++){
		    map[i][0] = '.';
		    map[i][W+1] = '.';
		}
		for(int i = 0; i <= W+1; i++){
		    map[0][i] = '.';
		    map[H+1][i] = '.';
		}
		string K;
		cin >> K;
		for(int i = 0; i < K.size(); i++){
			if(K[i] == '0') continue;
			key[K[i] - 'a' + 1] = 1;
		}
		solve();
	}
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요