[BOJ/백준 9328/C++] 열쇠

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

9328번: 열쇠

 

[문제 요약]

- 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

 

- 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

- 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

- 마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

- 상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

- 시간 제한 : 1초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 BFS를 이용한 구현+시뮬레이션 문제다.

 

먼저, 상근이는 빌딩 밖에 있다는 조건 때문에 BFS 시작할 위치를 따로 구해줘야 한다.

 

상근이가 빌딩에 들어가기 위해서는 문제에서 주어진대로 가장자리 벽이 아닌 곳을 통해 들어갈 수 있다는 점을 이용하여 주어지는 맵의 외곽을 확인 한 뒤 BFS를 돌려주어야 한다.

 

따라서 BFS를 수행하기 전에 맵의 외곽을 확인하는 작업이 필요하다.

vector<pii> start_point;
for (int i = 0; i < w; i++)
{
    if (map[0][i] == '.') start_point.push_back({ 0,i });
    else if (isBigAlpha(map[0][i]))
    {
        if (keys[map[0][i] - 'A'] == 1) { map[0][i] = '.'; start_point.push_back({ 0,i }); }
    }
    else if (isSmallAlpha(map[0][i]))
    {
        keys[map[0][i] - 'a'] = 1; map[0][i] = '.'; start_point.push_back({ 0,i });
    }
    else if (map[0][i] == '$')
    {
        get_doc++; map[0][i] = '.'; start_point.push_back({ 0,i });
    }

    if (map[h - 1][i] == '.') start_point.push_back({ h - 1,i });
    else if (isBigAlpha(map[h - 1][i]))
    {
        if (keys[map[h - 1][i] - 'A'] == 1) { map[h - 1][i] = '.'; start_point.push_back({ h - 1,i }); }
    }
    else if (isSmallAlpha(map[h - 1][i]))
    {
        keys[map[h - 1][i] - 'a'] = 1; map[h - 1][i] = '.'; start_point.push_back({ h - 1,i });
    }
    else if (map[h - 1][i] == '$')
    {
        get_doc++; map[h - 1][i] = '.'; start_point.push_back({ h - 1,i });
    }
}
for (int i = 0; i < h; i++)
{
    if (map[i][0] == '.') start_point.push_back({ i,0 });
    else if (isBigAlpha(map[i][0]))
    {
        if (keys[map[i][0] - 'A'] == 1) { map[i][0] = '.'; start_point.push_back({ i,0 }); }
    }
    else if (isSmallAlpha(map[i][0]))
    {
        keys[map[i][0] - 'a'] = 1; map[i][0] = '.'; start_point.push_back({ i,0 });
    }
    else if (map[i][0] == '$')
    {
        get_doc++; map[i][0] = '.'; start_point.push_back({ i,0 });
    }

    if (map[i][w - 1] == '.') start_point.push_back({ i,w - 1 });
    else if (isBigAlpha(map[i][w - 1]))
    {
        if (keys[map[i][w - 1] - 'A'] == 1) { map[i][w - 1] = '.'; start_point.push_back({ i,w - 1 }); }
    }
    else if (isSmallAlpha(map[i][w - 1]))
    {
        keys[map[i][w - 1] - 'a'] = 1; map[i][w - 1] = '.'; start_point.push_back({ i,w - 1 });
    }
    else if (map[i][w - 1] == '$')
    {
        get_doc++; map[i][w - 1] = '.'; start_point.push_back({ i,w - 1 });
    }
}

• '.' 의 경우는 start_point에 그냥 추가한다
• 대문자의 경우 해당하는 키(소문자)가 존재할 경우 위치를 '.'으로 바꾸고 start_point에 추가
• 소문자의 경우 key를 획득하는 것이기 때문에 keys에 열쇠획득 여부를 반영 후 '.'으로 바꾸고 start_point에 추가
• '$'의 경우 획득한 문서의 개수를 나타내는 get_doc변수를 하나 증가시키고 '.'으로 바꾼다음 start_point에 추가

 

다음으로 start_point 지점을 다 찾았으면 시작 지점들을 queue에 넣어준다음 bfs를 수행하면서 문서들을 찾아주면된다.

move = false;

vector<vector<bool>> ck(h, vector<bool>(w, 0));
queue<pii> q;
for (int i = 0; i < start_point.size(); i++)
{
    q.push(start_point[i]);
    ck[start_point[i].first][start_point[i].second] = true;
}

while (!q.empty())
{
    pii tmp = q.front(); q.pop();

    for (int i = 0; i < 4; i++)
    {
        int nx = tmp.second + dx[i];
        int ny = tmp.first + dy[i];

        if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
        if (ck[ny][nx]) continue;
        if (map[ny][nx] == '*') continue;

        if (isBigAlpha(map[ny][nx]))
        {
            if (keys[map[ny][nx] - 'A'] == 1)
            {
                map[ny][nx] = '.';
                ck[ny][nx] = true;
                q.push({ ny,nx });
                move = true;
            }
            else continue;
        }
        else if (isSmallAlpha(map[ny][nx]))
        {
            keys[map[ny][nx] - 'a'] = 1;
            map[ny][nx] = '.';
            ck[ny][nx] = true;
            q.push({ ny,nx });
            move = true;
        }
        else if (map[ny][nx] == '.')
        {
            ck[ny][nx] = true;
            q.push({ ny,nx });
        }
        else if (map[ny][nx] == '$')
        {
            ck[ny][nx] = true;
            map[ny][nx] = '.';
            q.push({ ny,nx });
            get_doc++;
            move = true;
        }
    }
}

 

이때 처음 초기화한 move변수는 BFS를 수행하면서 열쇠획득, 문 열기, 문서 획득과 같은 map상에서 업데이트가 일어나는 경우들이 발생하지 않으면 move변수는 false상태로 존재한다.

 

따라서 BFS를 다 수행했을 때 move변수가 false라면 더 이상 BFS를 수행하는 의미가 없기 때문에 그동안 계산했던 get_doc변수를 리턴하면서 BFS를 종료하게 된다.

 

[전체 소스코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <set>

#define INF 987654321
#define mod 1000000007
#define pii pair<int,int>
#define MAX 7
#define ll long long

using namespace std;

int h, w;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

bool isBigAlpha(char input)
{
	if (input >= 'A' && input <= 'Z') return true;
	else return false;
}

bool isSmallAlpha(char input)
{
	if (input >= 'a' && input <= 'z') return true;
	else return false;
}

int bfs(int h, int w, vector<vector<char>>& map, vector<int> &keys)
{
	bool move = false;
	int get_doc = 0;
	while (1)
	{
		vector<pii> start_point;
        //사전작업, 시작지점 찾기
		for (int i = 0; i < w; i++)
		{
			if (map[0][i] == '.') start_point.push_back({ 0,i });
			else if (isBigAlpha(map[0][i]))
			{
				if (keys[map[0][i] - 'A'] == 1) { map[0][i] = '.'; start_point.push_back({ 0,i }); }
			}
			else if (isSmallAlpha(map[0][i]))
			{
				keys[map[0][i] - 'a'] = 1; map[0][i] = '.'; start_point.push_back({ 0,i });
			}
			else if (map[0][i] == '$')
			{
				get_doc++; map[0][i] = '.'; start_point.push_back({ 0,i });
			}

			if (map[h - 1][i] == '.') start_point.push_back({ h - 1,i });
			else if (isBigAlpha(map[h - 1][i]))
			{
				if (keys[map[h - 1][i] - 'A'] == 1) { map[h - 1][i] = '.'; start_point.push_back({ h - 1,i }); }
			}
			else if (isSmallAlpha(map[h - 1][i]))
			{
				keys[map[h - 1][i] - 'a'] = 1; map[h - 1][i] = '.'; start_point.push_back({ h - 1,i });
			}
			else if (map[h - 1][i] == '$')
			{
				get_doc++; map[h - 1][i] = '.'; start_point.push_back({ h - 1,i });
			}
		}
		for (int i = 0; i < h; i++)
		{
			if (map[i][0] == '.') start_point.push_back({ i,0 });
			else if (isBigAlpha(map[i][0]))
			{
				if (keys[map[i][0] - 'A'] == 1) { map[i][0] = '.'; start_point.push_back({ i,0 }); }
			}
			else if (isSmallAlpha(map[i][0]))
			{
				keys[map[i][0] - 'a'] = 1; map[i][0] = '.'; start_point.push_back({ i,0 });
			}
			else if (map[i][0] == '$')
			{
				get_doc++; map[i][0] = '.'; start_point.push_back({ i,0 });
			}

			if (map[i][w - 1] == '.') start_point.push_back({ i,w - 1 });
			else if (isBigAlpha(map[i][w - 1]))
			{
				if (keys[map[i][w - 1] - 'A'] == 1) { map[i][w - 1] = '.'; start_point.push_back({ i,w - 1 }); }
			}
			else if (isSmallAlpha(map[i][w - 1]))
			{
				keys[map[i][w - 1] - 'a'] = 1; map[i][w - 1] = '.'; start_point.push_back({ i,w - 1 });
			}
			else if (map[i][w - 1] == '$')
			{
				get_doc++; map[i][w - 1] = '.'; start_point.push_back({ i,w - 1 });
			}
		}

		move = false;

		vector<vector<bool>> ck(h, vector<bool>(w, 0));
		queue<pii> q;
		for (int i = 0; i < start_point.size(); i++)
		{
			q.push(start_point[i]);
			ck[start_point[i].first][start_point[i].second] = true;
		}

		//BFS
		while (!q.empty())
		{
			pii tmp = q.front(); q.pop();

			for (int i = 0; i < 4; i++)
			{
				int nx = tmp.second + dx[i];
				int ny = tmp.first + dy[i];

				if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
				if (ck[ny][nx]) continue;
				if (map[ny][nx] == '*') continue;

				if (isBigAlpha(map[ny][nx]))
				{
					if (keys[map[ny][nx] - 'A'] == 1)
					{
						map[ny][nx] = '.';
						ck[ny][nx] = true;
						q.push({ ny,nx });
						move = true;
					}
					else continue;
				}
				else if (isSmallAlpha(map[ny][nx]))
				{
					keys[map[ny][nx] - 'a'] = 1;
					map[ny][nx] = '.';
					ck[ny][nx] = true;
					q.push({ ny,nx });
					move = true;
				}
				else if (map[ny][nx] == '.')
				{
					ck[ny][nx] = true;
					q.push({ ny,nx });
				}
				else if (map[ny][nx] == '$')
				{
					ck[ny][nx] = true;
					map[ny][nx] = '.';
					q.push({ ny,nx });
					get_doc++;
					move = true;
				}
			}
		}

		if (!move) break;
	}
	return get_doc;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	while (T--)
	{
		cin >> h >> w;
		vector<vector<char>> map(h, vector<char>(w, 0));
		vector<int> keys(26, 0);
		
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				cin >> map[i][j];

		string tmp;
		cin >> tmp;
		if(tmp[0] != '0') for (int i = 0; i < tmp.size(); i++) keys[tmp[i] - 'a'] = 1;

		cout << bfs(h, w, map, keys) << "\n";
	}
}

굳