[백준 1941] 소문난 칠공주 (C++)

1941번: 소문난 칠공주

 

처음에 단순 dfs로 갔다가 ㅓㅏㅗㅜ 모양으로 탐색이 불가능해서 바로 접었다.

bfs로 다시 도전하는데 정점간의 상태정보를 공유할 수가 없어서 방법을 생각하다가 모든 경우의 수가 최대 25C7 = 48만으로 충분히 탐색 가능함을 깨닫고 dfs를 사용해서 상태 정보를 기록하고 구한 상태들이 서로 이어져 있는 경우를 찾는 방식으로 시도를 했다.

 

2차원 배열을 1차원 배열로 바꿔서 편하게 백트래킹을 할 수도 있었지만 굳이 내가 2차원 배열을 유지하면서 백트래킹을 해보려는 고집 때문에 시간이 오래 걸렸다.

 

2차원 배열 조합에서 83번째 라인이 정말 중요하다. 시작 행에서는 함수가 받은 인자의 sc부터 c를 증가시키지만 그 이후의 행부터는 c는 0부터 탐색해야했다.

나는 이걸 계속 인지하지 못하고 c를 계속 sc부터 증가시켜서 백트래킹으로 모두 탐색하지 못했다.. 결국 print 다 찍어보면서 알아채긴 했지만 삽질한다고 시간이 오래걸렸다.

 

상태를 구하면 bfs를 사용해서 선택된 공주들이 서로 이어져있는지 확인하면 된다.

처음 queue에는 공주들 중 한명의 좌표만 넣어주면 된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
 
using namespace std;
 
 
// 1:S, 2:Y
int Map[6][6];
bool princess[6][6];
int ans;
 
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
 
void input(){
    string str;
    for(int r = 0; r < 5; r++){
        cin >> str;
        for(int c = 0; c < 5; c++){
            if(str[c] == 'S') Map[r][c] = 1;
            else Map[r][c] = 2;
        }
    }
}
 
bool check(){
    int cnt = 0;
    bool tempvisited[6][6];
    memset(tempvisited, 0, sizeof(tempvisited));
    
    queue<pii > que;
    for(int r = 0; r < 5; r++){
        bool bb = false;
        for(int c = 0; c < 5; c++){
            if(princess[r][c]){
                que.push({r, c});
                tempvisited[r][c] = true;
                bb = true;
                break;
            }
        }
        if(bb) break;
    }
    
    while(!que.empty()){
        pii now = que.front();
        cnt++;
        que.pop();
        
        if(cnt == 7){
            return true;
        }
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            
            if(nr >= 5 || nr < 0 || nc >= 5 || nc < 0 || tempvisited[nr][nc]) continue;
            if(princess[nr][nc]){
                tempvisited[nr][nc] = true;
                que.push({nr, nc});
            }
        }
    }
    
    return false;
}
int cc = 0;
void back(int sr, int sc, int s, int y, int n){
    if(y >= 4) return;
    if(n == 7){
        if(s >= 4){
            if(check()) ans++;
        }
        return;
    }
    
    for(int r = sr; r < 5; r++){
        int c = (r == sr? sc:0);
        for(; c < 5; c++){
            if(princess[r][c]) continue;
            princess[r][c] = true;
            
            if(Map[r][c] == 1) back(r, c, s+1, y, n+1);
            else back(r, c, s, y+1, n+1);
            
            princess[r][c] = false;
        }
    }
}
 
void solve(){
    back(0, 0, 0, 0, 0);
    cout << ans;
}
 
int main(){
    input();
    solve();
    
    return 0;
}