이번 문제는 백트레킹을 통해 가능한 좌표들의 조합을 구하고, 해당 조합을 순회하며 연결되어 있는지 DFS를 통해 확인하도록 하였다. 조합을 구할 때에는 조합 하나가 완성 되었을 때, S가 4개 이상 존재하지 않으면 추가하지 않도록 하여 갯수를 줄였다.

Code

grid=[list(str(input())) for _ in range(5)]
answer=0
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
idxs=[(i, j) for i in range(5) for j in range(5)]
combs=[]
cnt=0
def get_combs(cur, comb):
    if cur==len(idxs):
        if len(comb)==7:
            if get_chk(comb):
                combs.append(comb)
        return
    if len(comb)>7:
        return
    get_combs(cur+1, comb+[idxs[cur]])
    get_combs(cur+1, comb)
def get_chk(comb):
    result=0
    for y, x in comb:
        if grid[y][x]=='S':
            result+=1
    return result>=4
def get_connect(y, x, comb):
    global cnt
    for i in range(4):
        ny, nx=y+dy[i], x+dx[i]
        if 0<=ny<5 and 0<=nx<5 and not visited[ny][nx] and (ny, nx) in set(comb):
            visited[ny][nx]=True
            cnt+=1
            get_connect(ny, nx, comb)
get_combs(0, [])
for comb in combs:
    cnt=0
    visited = [[False for _ in range(5)] for _ in range(5)]
    visited[comb[0][0]][comb[0][1]]=True
    get_connect(comb[0][0], comb[0][1], comb)
    if cnt==6:
        answer+=1
print(answer)