https://www.acmicpc.net/problem/1941

✍️ 첫번째 접근

'서로 가로나 세로로 반드시 인접해 있어야 한다.'는 것을 보자마자 BFS를 써야한다는 걸 캐치했다.
하지만 모든 경우에 대해서 BFS를 적용해야 하기 때문에 즉, 조합으로 나올 수 있는 모든 경우에 대해 어떻게 적용해야 할지 감이 안 왔다.

✍️ 두번째 접근

약간의 힌트를 받아, next_permutation을 사용해 조합으로 나올 수 있는 모든 경우에 대해 적용했다. 이렇게 해서 풀긴 풀었지만 혼자만의 힘으로 푼 것이 아니기 때문에 추후에 다시 풀어볼 예정이다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
char board[5][5];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool mask[25];
int ans;
int main(void) {
    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(mask+7,mask+25,true);

    do {
        queue<pair<int, int> > Q;
        bool visit[5][5] = {false,};
        bool isp7[5][5] = {false,};
        int dasom = 0, total = 0;
        for(int i = 0; i < 25; i++) {
            if(!mask[i]) {
                int x = i / 5;
                int y = i % 5;
                isp7[x][y] = true;
                if(Q.empty()) {
                    Q.push(make_pair(x,y));
                    visit[x][y] = 1;
                }
            }
        }
        while(!Q.empty()) {
            pair<int,int> cur = Q.front();
            Q.pop();
            ++total;
            if(board[cur.X][cur.Y] == 'S')
                ++dasom;
            for(int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx > 4 || ny < 0 || ny > 4)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(!isp7[nx][ny])
                    continue;
                Q.push(make_pair(nx,ny));
                visit[nx][ny] = 1;
            }
        }
        if(total >= 7 && dasom >= 4)
            ++ans;
    } while(next_permutation(mask,mask+25));
    
    cout << ans;

    return 0;
}