[BOJ] 소문난 칠공주 - 1941

📃 문제

[BOJ] 소문난 칠공주 🔗링크

❓ 문제 접근

1. 시뮬레이션 문제인데, 각 케이스가 아래 조건에 맞는지 확인해야한다.
   • 조건 1. 25명 중 7명을 선택해야 한다.
   • 조건 2. 7명은 가로 또는 세로로 인접해야 한다.
   • 조건 3. 7명 중 적어도 4명 이상은 이다솜파 학생이어야 한다.
2. 조건 1은 재귀를 사용하여 구현했다. make7Princess()
   : 재귀를 사용하여 7명의 학생을 선택하는 모든 경우의 수를 확인했다.
   경우의 수는 25C7 = 480,700으로 주어진 시간 내에 계산 가능했다.
3. 조건 2는 DFS를 사용하여 구현했다. isConnected() DFS()
   : 첫번째 학생의 좌표를 받아 이 학생과 인접한 학생이 7명인지 확인했다.
4. 조건 3은 단순 배열 탐색으로 구현했다. isSomMoreThanFour()

🧠 풀이

#include <iostream>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int princessCase = 0;
int connectCount = 0;
int somCount = 0;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int visit[5][5] = {0,};
int selected[5][5] = {0,};
char map[5][5];
vector<pair<int,int>> princesses;

void make7Princess(int num);
bool isConnected();
void DFS(int y, int x);
bool isSomMoreThanFour();

int main(int argc, const char * argv[]) {
    
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            cin >> map[i][j];
        }
    }
    
    make7Princess(-1);
    
    cout << princessCase;
    return 0;
}

void make7Princess(int num){
    if(princesses.size() < 7){
        for(int i=num+1; i<25; i++){
            int y = i / 5;
            int x = i % 5;
        
            selected[y][x] = 1;
            princesses.push_back(make_pair(y,x));
            make7Princess(i);
            selected[y][x] = 0;
            princesses.pop_back();
        }
    }
    else{
        if(isConnected() && isSomMoreThanFour()){
            princessCase++;
        }
    }
}

bool isConnected(){
    memset(visit, 0, sizeof(visit));
    connectCount = 0;
    
    int y = princesses.front().first;
    int x = princesses.front().second;
    visit[y][x] = 1;
    connectCount++;
    DFS(y,x);
    
    if(connectCount >= 7)   return true;
    return false;
}

void DFS(int y, int x){
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(!(nx>=0 && nx<5 && ny>=0 && ny<5))   continue;
        if(!selected[ny][nx])   continue;
        if(visit[ny][nx])       continue;
        
        visit[ny][nx] = 1;
        connectCount++;
        DFS(ny, nx);
    }
}

bool isSomMoreThanFour(){
    somCount = 0;
    for(int i=0; i<princesses.size(); i++){
        int y = princesses[i].first;
        int x = princesses[i].second;
        
        if(map[y][x] == 'S')    somCount++;
    }
           
    if(somCount >= 4){
        return true;
    }
    return false;
}