[백트랙킹]백준1941번 소문난 칠공주

백준1941

정답률을 보고 흔한 백트랙킹 문제겠거니 했는데, 너무 고생했던 문제이다.

물론 많이 고생한만큼 크게 배우기도 했다.

일반적인 백트랙킹으로는 해결할 수 없는 문제였다.

백트랙킹으로는 한 번에 한 방향으로밖에 이동하지 못한다.

자신이 갈 수 있는 방향 중 하나를 고르고 해당 방향으로 갔을 때의 모든 경우의 수를 탐색하는 것이 백트랙킹이기 때문이다.

이 문제에서는 한 번에 한 방향이 아니라, 네 방향을 모두 탐색해야 한다.

심지어 네 방향만 보면 되는 것이 아니라, 상 하 좌 우 / 상하 상좌 상우 하좌 좌우 / 상하좌 상하우… 등 여러가지 조합을 모두 확인해야 했다.

따라서 문제를 조금 다르게 보는 시각이 중요했다.

학생은 25명으로 고정되어 있고, 25명의 학생들로 가능한 모든 조합을 생성한다.

모든 조합 중에서 조건을 만족하는 조합만 출력하면 된다.

백준 6603번 문제를 푸는 것과 똑같이 풀고, 마지막에 기저 조건에 도달했을 때만 문제에서 주어진 조건

• 이다솜파 학생이 4명 이상인지
• 선택된 7명의 학생이 모두 상,하,좌,우로 인접해 있는지를 확인하면 된다.

중복되는 조합은 포함하지 않아야 하기 때문에 현재 탐색한 인덱스 + 1을 매개변수로 두어 함께 넘겨준다.

(백트랙킹에서 중복 조합여부 구현 : https://yonghole.github.io/algorithm/BOJ6603/)

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;
char arr[25];
bool isused[25];
int num[7];
int y_iter[4] = {1,0,-1,0};
int x_iter[4] = {0,1,0,-1};
int cnt=0;
int s_count = 0;

bool checkAdjacent(){
    queue<pair<int, int> > q;
    int y = num[0] / 5;
    int x = num[0] % 5;
    int adj_count = 0;
    bool checked[25] = {false,};

    q.push(make_pair(y,x));
    checked[num[0]] = true;
    adj_count ++;

    while(!q.empty()){
        pair<int, int> cur = q.front();
        q.pop();
    
        for(int i=0;i<4;i++){
            int y = cur.first + y_iter[i];
            int x = cur.second + x_iter[i];

            if(y >=0 && x>=0 && y<5 && x < 5){
                int tmp = y * 5 + x;
                if(isused[tmp] && !checked[tmp]){
                    q.push(make_pair(y,x));
                    checked[tmp] = true;
                    adj_count ++;
                    if(adj_count==7){
                    return true;
                    }
                }
            }
        } 
    }
    return false;

}

void btk(int n, int start){
    // cout << n << " ";
    if(n==7){
        // check if s more than 4
        // check adjacency
        if(s_count >=4){
            if(checkAdjacent())
            cnt++;
        }
    return;
    }
    for(int i=start;i<25;i++){
        num[n] = i;
        if(arr[i]=='S'){
            s_count++;
        }
        isused[i] = true;
        btk(n+1,i+1);
        isused[i] = false;
        if(arr[i]=='S'){
            s_count--;
        } 
    }    
}

int main(){
    for(int i=0;i<5;i++){
        string a;
        cin >> a;
        for(int j=0;j<5;j++){
            arr[5*i+j] = a[j];
        }
    }

    btk(0,0);
    cout << cnt;
}