백준 - Keys(9328) 본문
https://www.acmicpc.net/problem/9328
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
해당 입력을 예시로 과정을 본다.
. . . . . . . . . . . . . . . . . . .
. * * * * * * * * * * * * * * * * * .
. . . . . . . . . . . . . . * * $ * .
. * B * A * P * C * * X * Y * . X . .
. * y * x * a * p * * $ * $ * * $ * .
. * * * * * * * * * * * * * * * * * .
. . . . . . . . . . . . . . . . . . .
둘러싸는 길을 만들어주면
생각하는 게 더 수월해진다.
대문자 알파벳의 위치정보를 map으로 관리해 준다.
처음 가지고 시작하는 키값을 확인하여
그래프에서 대문자를 제거하고 시작한다.
. . . . . . . . . . . . . . . . . . .
. * * * * * * * * * * * * * * * * * .
. . . . . . . . . . . . . . * * $ * .
. * B * A * P * . * * X * Y * . X . .
. * y * x * a * p * * $ * $ * * $ * .
. * * * * * * * * * * * * * * * * * .
. . . . . . . . . . . . . . . . . . .
이 상태에서 0,0 지점에서 BFS를 시작
나는 이동했던 경로를 #으로 바꿔가며 BFS를 진행했다.
BFS를 진행하는 조건은 3가지가 있다.
1. '.' 을 만나면 그대로 BFS를 진행
2. $를 만나면 정답 count를 올리고 BFS진행
마지막 소문자를 만났을 때가 핵심이다.
소문자를 만나면
대문자들의 위치정보를 저장해 둔 map을 활용해
전부 이동할 수 있는 경로인 '.'으로 대체한다.
그 후 bfs를 진행하기 위해 stack에 위치 정보를 넣어야 하는데
제거대상 대문자의 상하좌우에 #이 있는 경우
대문자 위치 정보를 stack에 넣는다.
# # # # # # # # # # # # # # # # # # #
# * * * * * * * * * * * * * * * * * #
# # # # # # # # # # # # # # * * # * #
# * B * # * # * # * * # * Y * # # # #
# * y * # * # * # * * # * $ * * # * #
# * * * * * * * * * * * * * * * * * #
# # # # # # # # # # # # # # # # # # #
왜 대문자의 위치정보를 다시 찾아 stack에 넣어야 하나면
전에 대문자를 이미 벽으로 인식하여 가지 않았기 때문에
키를 먹으면 탐색 위치를 다시 업데이트해야 한다.
코드가 좀 난잡하다.
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <map>
#include <cctype>
using namespace std;
vector<string> graph;
typedef pair<int, int> pp;
map<char, vector<pair<int, int>>> key_position;
int vec_y[4] = { 1, 0, -1, 0 };
int vec_x[4] = { 0, 1, 0, -1 };
int answer = 0;
void delete_door(char key) {
key = toupper(key);
if (key_position.find(key) != key_position.end()) {
for (int i = 0; i < key_position[key].size(); i++) {
graph[key_position[key][i].first][key_position[key][i].second] = '.';
}
}
}
void bfs() {
stack<pp> ss;
ss.push(pp(0, 0));
int size_y = graph.size();
int size_x = graph[0].size();
graph[0][0] = '#';
while (ss.size()) {
int y = ss.top().first;
int x = ss.top().second;
ss.pop();
for (int i = 0; i < 4; i++) {
int cur_y = y + vec_y[i];
int cur_x = x + vec_x[i];
if (cur_y < 0 || cur_y >= size_y || cur_x < 0 || cur_x >= size_x)
continue;
if (graph[cur_y][cur_x] != '*' || graph[cur_y][cur_x] != '#') {
if (graph[cur_y][cur_x] == '.') {
ss.push(pp(cur_y, cur_x));
graph[cur_y][cur_x] = '#';
}
else if (isalpha(graph[cur_y][cur_x]) && islower(graph[cur_y][cur_x])) {
char temp_key_upper = toupper(graph[cur_y][cur_x]);
delete_door(temp_key_upper);
ss.push(pp(cur_y, cur_x));
graph[cur_y][cur_x] = '#';
for (int k = 0; k < key_position[temp_key_upper].size(); k++) {
for (int vec_idx = 0; vec_idx < 4; vec_idx++) {
int cur_temp_y = key_position[temp_key_upper][k].first + vec_y[vec_idx];
int cur_temp_x = key_position[temp_key_upper][k].second + vec_x[vec_idx];
if (graph[cur_temp_y][cur_temp_x] == '#') {
ss.push(pp(key_position[temp_key_upper][k].first,
key_position[temp_key_upper][k].second));
graph[key_position[temp_key_upper][k].first][key_position[temp_key_upper][k].second] = '#';
break;
}
}
}
key_position.erase(temp_key_upper);
}
else if (graph[cur_y][cur_x] == '$') {
ss.push(pp(cur_y, cur_x));
graph[cur_y][cur_x] = '#';
answer += 1;
}
}
}
}
}
int main() {
int main_count;
cin >> main_count;
for (int mc = 0; mc < main_count; mc++) {
int n, m;
cin >> n >> m;
string add_temp = "";
for (int i = 0; i < m + 2; i++)
add_temp += ".";
graph.push_back(add_temp);
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
graph.push_back("." + temp + ".");
}
graph.push_back(add_temp);
for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph[0].size(); j++) {
if (isupper(graph[i][j]))
key_position[graph[i][j]].push_back(pp(i, j));
}
}
string key_temp;
cin >> key_temp;
for (int i = 0; i < key_temp.size(); i++) {
delete_door(key_temp[i]);
}
bfs();
cout << answer << endl;
graph.clear();
key_position.clear();
answer = 0;
}
}
'알고리즘' 카테고리의 다른 글
백준 - Sudoku(2239) (0) | 2024.04.04 |
---|---|
백준 - 파일 합치기(11066) (0) | 2024.03.12 |
백준 - 내리막 길(1520) (0) | 2024.03.08 |
백준 - LCS 2(9252) (0) | 2024.02.20 |
LeetCode - Number of Subarrays That Match a Pattern II (0) | 2024.02.15 |
Comments