BOJ 1941 [소문난 칠공주]

BOJ 소문난 칠공주 : https://www.acmicpc.net/problem/1941

안녕하세요. 이번 문제는 백준 온라인 저지의 [소문난 칠공주] 입니다.

먼저 문제를 해결하기 위해선, 

1. 7명의 학생을 추출한다.

2. 추출한 7명의 학생들이 서로 인접한지 확인한다.

이것이 핵심이었습니다.

먼저, 7명의 학생을 추출하는 과정은 DFS를 이용해 진행했습니다.

깊이가 7이 될 때까지, 각 인덱스를 증가시킵니다.

7명의 학생 선발이 모두 끝나면, 큐를 이용해 인접한지 체크해 나갑니다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
char classroom[25];
int princess[7];
bool closed[7];
bool Visited[5][5];
int Result = 0;
queue<int> q;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void DFS(int index, int depth, int cnt) {
    if(depth == 7) {
        if(cnt < 4)
            return;
        for(int i = 0; i < 5; i++)
            for(int j = 0; j< 5; j++)
                Visited[i][j] = false;
        int temp = 0;
        q.push(princess[0]);
        Visited[princess[0] / 5][princess[0] % 5] = true;
        while(!q.empty()) {
            temp++;
            int num = q.front();
            q.pop();
            int i = num / 5;
            int j = num % 5;
            for(int k = 0; k<4; k++) {
                for(int l = 0; l < 7; l++) {
                    if(((i + dx[k]) == (princess[l] / 5)) && ((j + dy[k]) == (princess[l] % 5))) {
                        if(!Visited[i + dx[k]][j + dy[k]]) {
                            Visited[i + dx[k]][j + dy[k]] = true;
                            q.push(princess[l]);
                        }
                    }
                }
            }
        }
        if(temp == 7)
            Result++;
        return;
    }
    for(int i = index+1; i < 25; i++) {
        princess[depth] = i;
        if(classroom[i] == 'S')
            DFS(i, depth + 1, cnt + 1);
        else
            DFS(i, depth + 1, cnt);
    }
}
int main() {
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            cin >> classroom[i*5 + j];
    for(int i = 0; i < 19; i++) {
        int cnt= 0;
        princess[0] = i;
        if(classroom[i] == 'S')
            cnt = 1;
        DFS(i, 1, cnt);
    }
    cout << Result << endl;
    return 0;
}