1941번 소문난 칠공주

백트래킹으로 풀려다가 안 풀려서, 다른 사람의 코드를 참고하였다.

문제에서

서로 가로나 세로로 반드시 인접해야한다.

라고 나와있다.

따라서, ┼ 같은 십자 모양은 DFS, 백트래킹으로 탐색할 수 없기 때문에 다른 아이디어가 필요하다.

문제의 조건을 요약하면 다음과 같다.

25명의 여학생들 중에서, 7명을 뽑는다. 7명 중 최소 4명 이상은 '이다솜파'여야 한다.

또한, 뽑은 7명의 학생들은 서로 서로 연결되어 있어야 한다. 

즉, 뽑은 7명의 학생이 연결되어있는지만 DFS로(chk 함수) 검사하면 된다.

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
 
using namespace std;
 
char student[5][5];
 
int result = 0;
 
int save[7] = { 0, };
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
bool visit[5][5] = { true, };
 
void chk(int r, int c)
{
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (0 <= y && y < 5 && 0 <= x && x < 5 && !visit[y][x])
        {
            chk(y, x);
        }
    }
}
 
void DFS(int n, int Y_count, int index)
{
    if (Y_count >= 4) return; // 임도연파가 4명 이상일 수 없다. by 문제 조건
 
    if (n == 7) // 7명
    {
        memset(visit, true, sizeof(visit));
 
        int chk_cnt = 0;
 
        for (int i = 0; i < n; i++)
        {
            int y = save[i] / 5;
            int x = save[i] % 5;
 
            visit[y][x] = false;
        }
 
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (!visit[i][j])
                {
                    ++chk_cnt;
 
                    if (chk_cnt >= 2) return; // 시간을 조금이라도 더 줄일 수 있다.
 
                    chk(i, j);
                }
            }
        }
 
        ++result;
 
        return;
    }
 
    for (int i = index; i <= 24; i++)
    {
        save[n] = i;
 
        if (student[i / 5][i % 5] == 'Y') DFS(n + 1, Y_count + 1, i + 1);
        else DFS(n + 1, Y_count, i + 1);
    }
}
 
 
int main(void)
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> student[i][j];
        }
    }
 
    DFS(0, 0, 0);
 
    printf("%d\n", result);
 
    return 0;
}