백준 - Keys(9328)

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

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;
    }
}