소문난 칠공주

코드

[ 실패 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int ans;
char board[5][5];
bool isused[5][5];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void func(int y, int x ,int depth, int Scnt){
    if(depth == 7){
        if(Scnt >= 4) ans++;
    }else{
        for(int dir=0;dir<4;dir++)
        {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if(ny <0 or nx <0 or nx>= 5 or ny >= 5) continue;
            if(isused[ny][nx]) continue;
            isused[ny][nx] = true;
            if(board[ny][nx] == 'S') func(ny, nx, depth+1, Scnt+1);
            else func(ny, nx, depth+1, Scnt);
            isused[ny][nx] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin >> board[i][j];
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
        {
            isused[i][j] = true;
            if(board[i][j] == 'S') func(i, j, 1, 1);
            else func(i, j, 1, 0);
            isused[i][j] = false;
        }

    cout << ans;
    return 0;
}

• 분석 이유
  : 백트래킹이 내가 생각한 경우의수를 만족시키지 않아서 분석할 가치가 있다고 생각

• 로직
  1) 모든 점들에 대해 4방향으로 백트래킹 실시
  2) depth == 7 이고 'S'가 4개 이상이면 ans++

• 실패 이유
  1) 해당 코드는 하나의 막대처럼 검사해서, 중간에 뻗어나가는 경우는 검사하지 못한다
  2) 시작은 다르지만, 같은 경우의수가 생김
  : 모든 점에 대해 검사하는 해당 코드에서 시작은 다르지만 결과적으로 같은 경우가 되는 중복이 발생
  --> 중복검사 하면 된다.(하지만 어차피 1번때문에 아예 걸러도 정답처리가 안됐었다)

---

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
char board[5][5];
int ch[25], ans;
vector<pair<int,int>> tmp(7);
// [ BFS ] - 모든 점이 이어저있는지 & S가 4개이상 있는지 검사 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool check(){
    bool b[5][5];
    bool vis[5][5];
    queue<pair<int,int>> q;
    for(int i=0;i<5;i++)
    {
        fill(b[i], b[i]+5, false);
        fill(vis[i], vis[i]+5, false);
    }
    for(int i=0;i<tmp.size();i++)
    {
        auto cur = tmp[i];
        b[cur.first][cur.second] = true;
    }
    q.push({tmp[0].first, tmp[0].second});
    vis[tmp[0].first][tmp[0].second] = true;
    int cnt=1;
    int scnt=0;
    if(board[tmp[0].first][tmp[0].second] == 'S') scnt++;
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if(ny<0 or nx<0 or ny>=5 or nx>=5) continue;
            if(vis[ny][nx] or !b[ny][nx]) continue;
            q.push({ny, nx});
            vis[ny][nx] = true;
            cnt++;
            if(board[ny][nx] == 'S') scnt++;
        }
    }
    if(cnt == 7 and scnt >= 4) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin >> board[i][j];
    fill(ch, ch+25, 1);
    for(int i=0;i<7;i++) ch[i] = 0;
    /* 25개중 7개를 고르는 조합 */
    do{
        int tc=0;
        for(int i=0;i<25;i++)
            if(!ch[i])
                tmp[tc++] = {i/5, i%5};
        if(check()) ans++;
    }while(next_permutation(ch, ch+25));
    cout << ans;
    return 0;
}

• 로직
  1) 25개중 7개를 고르는 조합을 구한다 (next_permutation)
  2) 7개의 점을 좌표화 해서 각 점들이 이어져있으며, 'S'가 4개 이상있는지 검사한다
  3) 1~2를 반복해서 ans++

• 후기
  BFS로 검사하고 이런게 상당히 귀찮을것같았는데 막상 오래 안걸리고,
  그냥 확실한 풀이가 떠오르면 바로 구현에 들어가는 것이 좋을것 같다 (시간초과는 고려해야함)