1. 연결되어 있는지 확인 하기 위해서 bfs 를 사용합니다. dfs 로는 십자모양을 검사할 수 없기 때문에 7개를 선정하는 과정은 맵이 아닌 단순하게 25C7 을 사용하여 선정합니다. 코드가 if 문이 길어서 시간초과가 나지 않고, 시간복잡도를 풀면 됩니다. |
/* 1. 25시7 조합을 만듭니다. 2. 에스가 4 이상인지 확인을 합니다. 3. 연결되어 있는지 확인을 합니다. 4. 위의 조건이 맞으면 정답++ 을 합니다. */ #include <iostream> #include <algorithm> #include <string> #include <queue> using namespace std; #define SIZE 5 int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int check_map[SIZE][SIZE]; int x, y, nx, ny; int dfs_visit[25]; string str; int S_cnt; int is7 = 0; struct point { int x, y; }; queue<point> que; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int ans; void problemIn() { for (int i = 0; i < 5; i++) { cin >> str; for (int j = 0; j < 5; j++) { map[i][j] = str[j]; } } } void check_map_init() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { check_map[i][j] = 0; visit[i][j] = 0; } } } void bfs() {
is7 = 0; while (!que.empty()) {
x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5) { if (check_map[nx][ny] == 1 && visit[nx][ny] == 0) { visit[nx][ny] = 1; que.push({ nx,ny }); is7++; } } } } } void dfs(int pos, int depth) { // 25C7 if (pos == 25 && depth == 7) { S_cnt = 0; for (int i = 0; i < 25; i++) { if (dfs_visit[i] == 1) { x = i / 5; y = i % 5; if (map[x][y] == 'S') { S_cnt++; } } } if (S_cnt >= 4) { // map 을 새로 만들어서 찾을 수 있는지 찾아보겠습니다. check_map_init(); for (int i = 0; i < 25; i++) { if (dfs_visit[i] == 1) { x = i / 5; y = i % 5; check_map[x][y] = 1; } } visit[x][y] = 1; que.push({ x,y }); bfs(); if (is7 == 6) { ans++; } } return; } if (pos == 25) return; dfs_visit[pos] = 1; dfs(pos + 1, depth + 1); dfs_visit[pos] = 0; dfs(pos + 1, depth); } void solve() { dfs(0, 0); } int main() { problemIn(); solve(); cout << ans << endl; return 0; } |