[Algorithm] Baekjoon 1941번 : 소문난 칠공주

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

1941번: 소문난 칠공주

struct Node
{
    int y;
    int x;
};
 
int maxCount = 7;
int answer = 0;
char arr[5][5];
bool visitedDFS[26];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<int> v;
 
 
Node oneToTwo(int n)
{
    Node node;
    node.y = n / 5;
    node.x = n % 5;
 
    return node;
}
 
 
bool BFS()
{
    queue<Node> q;
    int tempMap[5][5];
    memset(tempMap, 0, sizeof(tempMap));
    int count = 0;
 
    for (int i = 0; i < v.size(); ++i)
    {
        Node node = oneToTwo(v[i]);
 
        tempMap[node.y][node.x] = 1;
 
        if (i == 0)
        {
            q.push({ node.y,node.x});
            tempMap[node.y][node.x] = 0;
            ++count;
        }
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= 5) continue;
            if (nextX < 0 || nextX >= 5) continue;
            if (tempMap[nextY][nextX] == 0) continue;
 
            ++count;
            tempMap[nextY][nextX] = 0;
            q.push({ nextY,nextX});
        }
    }
    
    if (count == 7) return true;
    return false;
}
 
void DFS(int num, int count, int sCount)
{
    v.push_back(num);
 
 
    if (count == maxCount && sCount >= 4)
    {
        if (BFS())
        {
            ++answer;
        }
        return;
    }
    else if (count == maxCount) return;
 
    for (int i = num + 1; i < 25; ++i)
    {
        if (visitedDFS[i]) continue;
        visitedDFS[i] = true;
        Node node = oneToTwo(i);
 
        if (arr[node.y][node.x] == 'S')
        {
            DFS(i, count + 1, sCount + 1);
        }
        else
        {
            DFS(i, count + 1, sCount);
        }
 
        v.pop_back();
 
        visitedDFS[i] = false;
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < 25; ++i)
    {
        visitedDFS[i] = true;
 
        Node node = oneToTwo(i);
 
        if (arr[node.y][node.x] == 'S')
        {
            DFS(i, 1, 1);
        }
        else
        {
            DFS(i, 1, 0);
        }
 
        v.pop_back();
        visitedDFS[i] = false;
    }
 
 
    cout << answer;
}
 

 

내가 아직 안풀어본 문제의 유형이였다. N과M했을때 비스무리하게 하려다가 생각해보니 문제에서 제기하는 덩어리형태를 만들지 못하기 때문에 다른 사람 풀이를 보고나서야 풀 수 있었다.

 

당연히 문제에서의 조건에 맞는 형태를 만들어나가는 줄 알았는데, 그냥 무작위로 다 뽑은다음에 덩어리인지 검사하는 로직이였다. 이런 방식으로는 생각을 아예 못했었기 떄문에 첫시도에 못 풀었던 것 같다.

 

최대인원수는 25. 그래서 1 ~ 24까지 무작위로 사람을 뽑아서 vector에 넣는다. 사람을 뽑을때 다솜이파인지도 체크하면서 DFS를 수행하기 때문에 뽑은사람이 7명이면서 다솜이파가 4명일때 BFS를 수행한다.

우리가 뽑은 사람들이 한 덩어리인지 체크하기 위한 BFS이다. 

한 덩어리이면 ++answer을 해주고 최종적으로 answer을 출력해주면 된다.