9328번 열쇠

BFS 문제이다.

단지, 새로운 열쇠(a ~ z)를 획득하였을 때만, 주의 해주면 된다.

또한, map[y][x]를 '.'로 바꾸는 것도 신경쓰면 된다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
char map[102][102];
 
int dy[5] = { -1, 0, 1, 0, 0 };
int dx[5] = { 0, -1, 0, 1, 0 };
 
int h = 0, w = 0;
 
bool key[123] = { false, }; // z 값 = 122
 
int result = 0; // 답
 
bool update = true;
 
string alreadyKeys;
 
 
bool visit[102][102] = { false, };
 
void init()
{
    memset(visit, false, sizeof(visit));
    memset(key, false, sizeof(key));
    update = true;
    result = 0;
}
 
void BFS(int r, int c)
{
    queue<pair<int, int> > q;
 
    q.push({ r,c });
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int row = q.front().first;
            int column = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 5; i++)
            {
                int y = row + dy[i];
                int x = column + dx[i];
 
                if (0 <= y && y < h && 0 <= x && x < w && !visit[y][x] && map[y][x] != '*')
                {
                    if ('A' <= map[y][x] && map[y][x] <= 'Z')
                    {
                        if (key[(int)map[y][x] + 32])
                        {
                            q.push({ y, x });
                            map[y][x] = '.';
                            visit[y][x] = true;
                        }
                    }
                    else if ('a' <= map[y][x] && map[y][x] <= 'z')
                    {
                        key[(int)map[y][x]] = true;
                        q.push({ y, x });
                        map[y][x] = '.';
                        visit[y][x] = true;
                        update = true; 
                        // 새로운 열쇠를 먹었으므로, update 갱신.
                        // 즉, 다시 map을 처음부터 실행
                    }
                    else if (map[y][x] == '.' || map[y][x] == '$')
                    {
                        if (map[y][x] == '$')
                        {
                            ++result;
                            map[y][x] = '.';
                        }
 
                        q.push({ y, x });
                        visit[y][x] = true;
                    }
                }
            }
        }
    }
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        init();
 
        scanf("%d %d", &h, &w);
 
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> map[i][j];
            }
        }
 
        cin >> alreadyKeys;
 
        if (alreadyKeys[0] != '0')
        {
            int Size = alreadyKeys.length();
 
            for (int i = 0; i < Size; i++)
            {
                key[alreadyKeys[i]] = true;
            }
        }    
 
        while (update)
        {
            update = false;
 
            memset(visit, false, sizeof(visit));
 
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    if (i == 0 || j == 0 || i == h - 1 || j == w - 1)
                    {
                        if (map[i][j] == '.' || map[i][j] == '$')
                        {
                            BFS(i, j);
                        }
                        else if ('A' <= map[i][j] && map[i][j] <= 'Z')
                        {
                            if (key[(int)map[i][j] + 32])
                            {
                                BFS(i, j);
                            }        
                        }
                        else if ('a' <= map[i][j] && map[i][j] <= 'b')
                        {
                            key[(int)map[i][j]] = true;
 
                            BFS(i, j);
                        }
                    }
                }
            }
        }
 
        printf("%d\n", result);
    }
 
    return 0;
}