![](https://blog.kakaocdn.net/dn/W4Mdq/btsKuAvqkIC/JQiavs2mRuyx6TC6VSzfZ0/img.png)
일반적인 DFS라고 생각을 했으나, 한길로 이어진 모양이 아니라 ㅗ모양 ㅜ모양등 여러 갈래로 나뉘는 모양이 가능해서 일반적인 DFS로는 해결할 수 없었다.
마침 배열의 크기도 5x5라는 작은 숫자로 정해져있는만큼 그냥 모든 경우의 수를 조합으로 구해서 해당 경우가 문제의 조건을 만족하는지 확인하는 방식으로 해결하였다.
먼저 조합으로 7개의 위치를 뽑은 뒤, 해당 위치가 인접해있는지 BFS로 검사하였고 S의 개수도 함께 검사해주었다.
조건을 모두 만족한다면 Answer의 값을 1만큼 증가시키고 모든 경우를 다 탐색한 뒤에 답을 출력하도록 하였다.
#include <iostream>
#include <vector>
#include <queue>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
std::vector<std::vector<char>> Map;
int Answer = 0;
void Check(std::vector<std::pair<int, int>>& _Indexes)
{
static std::vector<std::vector<int>> NearCheck(5, std::vector<int>(5));
static std::vector<int> DirX = { 0, 1, 0, -1 };
static std::vector<int> DirY = { -1, 0, 1, 0 };
for (int i = 0; i < _Indexes.size(); i++)
{
auto [Y, X] = _Indexes[i];
NearCheck[Y][X] = 1;
}
//Y, X
std::queue<std::pair<int, int>> BFS;
BFS.push(_Indexes[0]);
NearCheck[_Indexes[0].first][_Indexes[0].second] = 0;
int NearCount = 0;
int SomCount = 0;
while (BFS.size() > 0)
{
auto [CurY, CurX] = BFS.front();
BFS.pop();
NearCount++;
if (Map[CurY][CurX] == 'S')
{
SomCount++;
}
for (int i = 0; i < 4; i++)
{
int NextX = CurX + DirX[i];
int NextY = CurY + DirY[i];
if (NextX < 0 || NextY < 0 || NextX >= 5 || NextY >= 5)
{
continue;
}
if (NearCheck[NextY][NextX] != 1)
{
continue;
}
NearCheck[NextY][NextX] = -1;
BFS.push({ NextY, NextX });
}
}
if (NearCount == 7 && SomCount >= 4)
{
Answer++;
}
for (int i = 0; i < _Indexes.size(); i++)
{
auto [Y, X] = _Indexes[i];
NearCheck[Y][X] = 0;
}
}
void Combination(const std::vector<std::vector<std::pair<int, int>>>& _Indexes, int _CurIndex, int _CurSize)
{
static std::vector<std::pair<int, int>> Selected(7);
if (_CurSize == 7)
{
Check(Selected);
return;
}
for (int i = _CurIndex; i < 25; i++)
{
Selected[_CurSize] = _Indexes[i / 5][i % 5];
Combination(_Indexes, i + 1, _CurSize + 1);
}
}
int main()
{
Init();
Map.resize(5, std::vector<char>(5, 0));
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
std::cin >> Map[i][j];
}
}
std::vector<std::vector<std::pair<int, int>>> Indexs(5, std::vector<std::pair<int, int>>(5));
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
Indexs[i][j] = { i, j };
}
}
Combination(Indexs, 0, 0);
std::cout << Answer;
return 0;
}
'매일매일 코테풀기 (일시 중단!)' 카테고리의 다른 글
(2024-11-03) 1 문제 : 백준 - 2560 (짚신벌레) (1) | 2024.11.03 |
---|---|
(2024-11-02) 2 문제 : 백준 - 22945 (팀 빌딩) (0) | 2024.11.02 |
(2024-11-01) 2 문제 : 백준 - 1937 (욕심쟁이 판다) (0) | 2024.11.01 |
(2024-11-01) 1 문제 : 백준 - 1103 (서울 지하철 2호선) (0) | 2024.11.01 |
(2024-10-31) 5 문제 : 백준 - 1103 (게임) (0) | 2024.10.31 |