Coding/백준

1941번 소문난 칠공주

labote 2020. 4. 17. 04:16

 백트래킹 문제.

 

 1. 5x5로 25개 고정이므로 25명 중 7명을 고른다. (6603번 로또 참고, https://www.acmicpc.net/problem/6603).

 2. 7명 중 이다솜파(S)가 4명 이상인지 확인한다.

 3. 이다솜파가 4명 이상이면 7명이 붙어있는지 확인한다(BFS).

 

참고)

 

x의 좌표 => 해당 숫자/5

y의 좌표 => 해당 숫자%5

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <vector>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 6
 
using namespace std;
 
typedef pair<int,int> pir;
char girls[MAX][MAX];
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int map[MAX][MAX];
bool v[MAX][MAX];
int order[7];
int store[26];
vector<int> vec;
queue<pir> q;
int ans;
 
 
bool Attachedchecked(){
    int cnt=1;
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx=x+xx[i];
            int ny=y+yy[i];
            
            if(nx<0 || ny<0 || nx>=5 || ny>=5) continue;
            if(!v[nx][ny] && map[nx][ny]==1){
                v[nx][ny]=visited;
                cnt++;
                q.push(pir(nx,ny));
            }
        }
    }
    
    if(cnt==7){
        return true;
    }
    else{
        return false;
    }
    
}
 
bool Schecked(){
    int cnt=0;
    
    for(int i=0;i<7;i++){
        int x=vec[i]/5;
        int y=vec[i]%5;
        
        if(girls[x][y]=='S'){
            cnt++;
        }
        
        if(cnt>=4){
            q.push(pir(x,y));
            v[x][y]=visited;
            return true;
        }
    }
    
    return false;
}
 
void Clear(){
    
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            map[i][j]=0;
            v[i][j]=Non_visited;
        }
    }
    
    while(!q.empty()){
        q.pop();
    }
    
    while(!vec.empty()){
        vec.pop_back();
    }
}
 
void Combination(int step, int cnt){
    if(cnt==7){
        
        for(int i=0;i<7;i++){
            vec.push_back(order[i]);
        }
        
        if(Schecked()){
            for(int i=0;i<7;i++){
                int x=vec[i]/5;
                int y=vec[i]%5;
                
                map[x][y]=1;
            }
            
            if(Attachedchecked()){
                ans++;
            }
        }
        
        Clear();
        
        return;
    }
    else{
        for(int i=step;i<25;i++){
            order[cnt]=store[i];
            Combination(i+1, cnt+1);
        }
    }
}
 
int main(){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            cin >> girls[i][j];
        }
    }
    
    for(int i=0;i<25;i++){
        store[i]=i;
    }
    
    Combination(0, 0);
    
    cout << ans << endl;
}
 
 cs