백준/9328번/열쇠/골드1

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

문제 설명

Site: Baekjoon
Number: 9328
Category: BFS
Rank: Gold 1

열쇠, 문, 서류가 존재하는 맵에서 먹을 수 있는 서류의 최대 갯수를 구하는 문제입니다.

문제 풀이

열쇠를 비트 연산을 통해 하나의 int변수에 저장하여 문을 열 수 있는지 여부를 비트 연산을 통해 판단하고, 서류는 중복으로 먹는 상황을 방지하기 위해 2차원 bool doc배열로 관리하였습니다.

테스트케이스 수를 T에 저장하고 하나씩 줄이며 계산합니다.

각 테스트케이스 별로 visited와 doc배열을 리셋하고 외곽에서 시작할 수 있는 점을 파악하여 진행하였습니다.

외곽에서 진행할 수 있는 점을 모두 돌며 먹을 수 있는 열쇠와 서류를 먹은 후 다시 모든 점을 돌며 진행하며, 서류와 열쇠의 값에 변화가 없다면 더이상 먹을 수 있는 것이 없다고 판단하여 종료합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define PII pair<int, int>

using namespace std;

char arr[101][101];
bool visited[101][101];
bool doc[101][101];

int dirx[4] = { 0, -1, 0, 1 };
int diry[4] = { -1, 0, 1, 0 };

bool IsDoor(const char& c)
{
    if (c >= 'A' && c <= 'Z')
        return true;
    return false;
}

bool IsKey(const char& c)
{
    if (c >= 'a' && c <= 'z')
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        int h, w;
        cin >> h >> w;

        vector<PII> starting_points;
        int keys = 0;
        int documents = 0;

        for(int i = 0; i < h; i++)
	        for(int j = 0; j < w; j++)
                cin >> arr[i][j];

    	string keystr;
        cin >> keystr;

        if(keystr != "0")
        {
            for (int i = 0; i < keystr.length(); i++)
                keys |= 1 << (keystr[i] - 97);
        }

        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (arr[i][j] != '*')
                {
                    starting_points.emplace_back(i, j);
                }
                if (i != 0 && i != h - 1)
                    j += w - 2;
            }
        }

        int tmpkeys = -1;
        int tmpdocuments = -1;

    	while(tmpkeys != keys || tmpdocuments != documents)
        {
            tmpkeys = keys;
            tmpdocuments = documents;

            for(int i = 0; i < starting_points.size(); i++)
            {
                queue<PII> q;
                q.push(starting_points[i]);

                memset(visited, false, sizeof(visited));

                visited[starting_points[i].first][starting_points[i].second] = true;

                while(!q.empty())
                {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();

                    if (arr[x][y] == '$' && doc[x][y] == false)
                    {
                        documents++;
                        doc[x][y] = true;
                    }
                    else if (IsKey(arr[x][y]))
                        keys |= 1 << (arr[x][y] - 97);
                    else if (IsDoor(arr[x][y]) && ((keys | 1 << (arr[x][y] - 65)) != keys))
                        continue;

                    for(int i = 0; i < 4; i++)
                    {
                        int newx = x + dirx[i];
                        int newy = y + diry[i];

                        if (newx >= h || newx < 0 || newy >= w || newy < 0 || visited[newx][newy] == true || arr[newx][newy] == '*')
                            continue;

                        visited[newx][newy] = true;
                        q.emplace(newx, newy);
                    }
                }

            }
        }
        memset(doc, false, sizeof(doc));
        cout << documents << '\n';
    }

    return 0;
}