[ C++ 백준 9328 ] 열쇠
2023. 11. 15. 16:00ㆍ알고리즘/백준 문제풀이
일단 문제를 이해해보자.
이렇게 입력이 된 테스트 케이스에서 답이 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인지 잘 모르겠다.
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[ C++ 백준 1149 ] RGB거리 (0) | 2024.05.08 |
---|---|
[ C++ 백준 1167, 1967 ] 트리의 지름, 트리의 지름 (0) | 2024.05.07 |
[ C++ 백준 9466 ] 텀 프로젝트 (0) | 2023.11.09 |
[ C++ 백준 7785 ] 회사에 있는 사람 (0) | 2023.11.07 |
[ C++ 백준 2805 ] 나무 자르기 (0) | 2023.11.04 |