백준 9328 / 열쇠

난 아직 멀었다는 생각이 들었다.

쉽게 풀 수 있는 문제를 어렵게 접근했던 것 같다.

처음엔 문제의 조건 그대로 구현하려했다.

BFS를 돌리되, priority_queue를 이용하여 

획득한 파일의 개수, 좌표, 획득한 키(string으로 저장), 획득한 파일의 좌표

를 계속 넘기며 정답을 찾으려 했다.

50%에서 자꾸 메모리 초과가 나서 다 지우고 로직을 새로 세웠다.

문제는 쉽다.

우선, 상근이는 빌딩 밖으로 나갈 수 있기 때문에 맵 주변에 빈칸을 생성해준다.

열쇠나 파일을 찾을 때마다 다시 0,0,으로 돌아와 bfs를 돌리면 된다.

문을 열거나 파일을 찾으면 맵을 빈칸으로 갱신하고 다시 0,0으로 돌아온다면 그 문을 지나가거나 파일이 있던 곳에 접근할 수 있다.

열쇠를 획득하는 건 map을 사용했다.

코드

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<memory.h>
#include<map>
#include<string>
 
using namespace std;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
map<char, bool>key;
 
char pmap[105][105];
bool check[105][105];
 
bool findkey;
 
int h, w;
int ans = 0;
 
void bfs(int a, int b) {
 
    queue<pair<int, int>>q;
    q.push({ a,b });
    check[a][b] = true;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
                if (check[nx][ny] == false) {
                    if (pmap[nx][ny] == '.') {
                        check[nx][ny] = true;
                        q.push({ nx,ny });
                    }
                    if (pmap[nx][ny] == '$') {
                        ans++;
                        pmap[nx][ny] = '.';
                        check[nx][ny] = true;
                        findkey = true;
                        q.push({ nx,ny });
                    }
                    if (pmap[nx][ny] >= 'A' && pmap[nx][ny] <= 'Z') {
 
                        if (key.count(pmap[nx][ny] - 'A' + 'a') != 0) {
                            pmap[nx][ny] = '.';
                            check[nx][ny] = true;
                            q.push({ nx,ny });
                        }
                    }
                    if (pmap[nx][ny] >= 'a' && pmap[nx][ny] <= 'z') {
                        key[pmap[nx][ny]] = true;
                        check[nx][ny] = true;
                        findkey = true;
                        pmap[nx][ny] = '.';
                        q.push({ nx,ny });
                    }
                }
            }
        }
    }
}
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    cin >> testcase;
 
    while (testcase--) {
    
        key.clear();
        ans = 0;
        cin >> h >> w;
        
        for (int i = 0; i < h + 2; i++) {
            for (int j = 0; j < w + 2; j++) {
                if (i == 0 || i == h + 1 || j == 0 || j == w + 1) {
                    pmap[i][j] = '.';
                }
                else {
                    cin >> pmap[i][j];
                }
            }
        }
 
        h = h + 2;
        w = w + 2;
 
        string tmp;
        cin >> tmp;
        for (char c : tmp) {
            key[c] = true;
        }
    
        findkey = true;
 
        while (findkey) {
 
            findkey = false;
            memset(check, false, sizeof(check));
 
            bfs(0, 0);
        }
 
        cout << ans << endl;
    }
 
}