[ C++ 백준 9328 ] 열쇠

문제_링크

9328번: 열쇠

---

 

---

 

 

일단 문제를 이해해보자.

이렇게 입력이 된 테스트 케이스에서 답이 3이 나오게 된다.

 

일단 c와 z 열쇠를 가지고 시작한다.

c열쇠로 C문을 열고 들어가서 p열쇠를 얻을 수 있다.

p열쇠로 P문을 열고 들어가서 a열쇠를 얻을 수 있다.

a열쇠로 A문을 열고 들어가서 x열쇠를 얻을 수 있다.

x열쇠로 X문을 열고 들어가서 문서 하나를 획득할 수 있다.

오른쪽에 뚤려있는 공간으로 들어가서 X문을 열고 문서 두개를 획득할 수 있다.

 

이런 식으로 진행되는 것을 보고 BFS를 짜면 된다.

시간 초과가 안 나도록 짜는 것이 중요해보였다.

 

일단은 char형으로 입력된 것을 visited로 기억해서 만약 a열쇠를 얻었을 때

A문이 visited라면 A문을 큐에 넣어서 그 위치부터 다시 찾도록 알고리즘을 짜보았다.

 

#include <iostream>
#include <string.h>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

char arr[101][101];
bool visited[101][101];
unordered_map<char, vector<pair<int, int>>> chInfo;
// char = 문, pair<int,int> = 위치
//X문이 여러개 있을 수 있다.

int documentCnt = 0;

int dirX[4] = { 1, 0, -1, 0 };
int dirY[4] = { 0, 1, 0, -1 };

void CheckKey(char key)
{
	if (key == '0')
		return;

	for (auto door : chInfo[key + 'A' - 'a'])
	{
		int doorX = door.first;
		int doorY = door.second;

		arr[doorY][doorX] = '.';
	}
}

void BFS(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x, y });

	visited[y][x] = true;
	//열쇠 체크
	if ('a' <= arr[y][x] && arr[y][x] <= 'z')
	{
		for (auto door : chInfo[arr[y][x] + 'A' - 'a'])
		{
			int doorX = door.first;
			int doorY = door.second;

			if (visited[doorY][doorX] == true)
				q.push(door);

			arr[doorY][doorX] = '.';
		}

		arr[y][x] = '.';
	}
	//문서 체크
	else if (arr[y][x] == '$')
	{
		documentCnt++;
		arr[y][x] = '.';
	}
	else if (arr[y][x] != '.')
		return;

	while (!q.empty())
	{
		pair<int, int> pos = q.front();
		q.pop();

		int x = pos.first;
		int y = pos.second;

		if (arr[y][x] == '*')
			continue;

		for (int i = 0; i < 4; ++i)
		{
			int dx = x + dirX[i];
			int dy = y + dirY[i];

			if (visited[dy][dx] == true)
				continue;
			
			visited[dy][dx] = true;

			// 조건 처리
			// *이라면 갈 수 없다.
			if (arr[dy][dx] == '*' || arr[dy][dx] == '\0')
				continue;
			// 문이라면 갈 수 없다.
			else if ('A' <= arr[dy][dx] && arr[dy][dx] <= 'Z')
				continue;

			// 열쇠라면 문들을 전부 열어두고
			// 이미 갔던 문이라면 큐에 넣는다.
			if ('a' <= arr[dy][dx] && arr[dy][dx] <= 'z')
			{
				for (auto door : chInfo[arr[dy][dx] + 'A' - 'a'])
				{
					int doorX = door.first;
					int doorY = door.second;

					if (visited[doorY][doorX] == true)
						q.push(door);

					arr[doorY][doorX] = '.';
				}

				arr[dy][dx] = '.';
			}

			// 문서라면 카운트를 올린다.
			if (arr[dy][dx] == '$')
			{
				documentCnt++;
				arr[dy][dx] = '.';
			}

			if (arr[dy][dx] == '.')
				q.push({ dx, dy });
		}
	}
}

int main()
{
	int testCaseCnt;
	cin >> testCaseCnt;

	for (int tc = 0; tc < testCaseCnt; ++tc)
	{
		int height, width;
		cin >> height >> width;
		
		//구조 입력
		string inputStr;
		for (int y = 1; y <= height; ++y)
		{
			cin >> inputStr;
			for (int x = 1; x <= width; ++x)
			{
				arr[y][x] = inputStr[x-1];

				// 문 정보 입력하기
				if ('A' <= arr[y][x] && arr[y][x] <= 'Z')
				{
					chInfo[arr[y][x]].push_back({ x, y });
				}
			}
		}
		//열쇠값 입력
		cin >> inputStr;
		for (int i = 0; i < inputStr.length(); ++i)
			CheckKey(inputStr[i]); // 열쇠로 열 수 있는 문 열어두기

		// 외곽 ( 테두리 부분 탐색 )
		for (int x = 1; x <= width; ++x)
		{
			BFS(x, 1);
			BFS(x, height);
		}

		for (int y = 1; y <= height; ++y)
		{
			BFS(1, y);
			BFS(width, y);
		}

		cout << documentCnt << '\n';

		// 초기화
		documentCnt = 0;
		chInfo.clear();
		memset(visited, false, sizeof(visited));
		memset(arr, '/0', sizeof(arr));
	}
}

약간의 하드코딩이 있지만 해결했다.

 

---

개인적인 평가

난이도 : C

걸린 시간 : 약 1시간

 

BFS만 알면 풀기 쉬운 문제다.

왜 골드 1인지 잘 모르겠다.