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

---

1. 포함/불포함 풀이

from collections import deque


def bfs(x, y):
    q = deque()
    maps = [[False] * 5 for _ in range(5)]
    q.append((x, y))
    maps[x][y] = True
    cnt = 1
    while q:
        x, y = q.popleft()
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < 5 and 0 <= ny < 5 and not maps[nx][ny] and visited[nx][ny]:
                q.append((nx, ny))
                maps[nx][ny] = True
                cnt += 1
    return cnt == 7


def check():
    for i in range(5):
        for j in range(5):
            if visited[i][j]:
                return bfs(i, j)


# 학생번호, 포함학생수, 다솜파학생수
def dfs(idx, cnt, scnt):
    global ans
    if cnt > 7:  # 백트래킹
        return

    if idx == 25:
        if cnt == 7 and scnt >= 4:  # 7명 그룹이고, 4명 이상이 다솜파인 경우
            if check():
                ans += 1  # 정답이면 + 1
        return

    # 현재 idx 를 포함하는 경우
    visited[idx // 5][idx % 5] = True
    if arr[idx // 5][idx % 5] == 'S':
        dfs(idx + 1, cnt + 1, scnt + 1)
    else:
        dfs(idx + 1, cnt + 1, scnt)
    visited[idx // 5][idx % 5] = False

    # 현재 idx 를 포함하지 않는 경우
    dfs(idx + 1, cnt, scnt)


arr = [input() for _ in range(5)]
ans = 0
visited = [[False] * 5 for _ in range(5)]
dfs(0, 0, 0)
print(ans)

2. 조합 방식의 풀이

from collections import deque


def bfs(x, y):
    q = deque()
    maps = [[False] * 5 for _ in range(5)]
    q.append((x,y))
    maps[x][y] = True
    cnt = 1
    while q:
        x,y = q.popleft()
        for dx,dy in ((-1,0), (1,0), (0,-1), (0,1)):
            nx,ny = x+dx, y+dy
            if 0<=nx<5 and 0<=ny<5 and not maps[nx][ny] and visited[nx][ny]:
                q.append((nx,ny))
                maps[nx][ny] = True
                cnt += 1
    return cnt==7


def check():
    for i in range(5):
        for j in range(5):
            if visited[i][j]:
                return bfs(i, j)


# 포함학생수, 학생번호, 다솜파학생수
def dfs(cnt, idx, scnt):
    global ans
    if cnt > 7:
        return

    if cnt==7 and scnt>=4:
        if check():
            ans += 1  # 정답이면 + 1
        return

    for i in range(idx, 25):
        visited[i//5][i%5] = True
        if arr[i//5][i%5] == 'S':
            dfs(cnt+1, i+1, scnt+1)
        else:
            dfs(cnt+1, i+1, scnt)
        visited[i//5][i%5] = False


arr = [input() for _ in range(5)]
ans = 0
visited = [[False] * 5 for _ in range(5)]
dfs(0, 0, 0)
print(ans)

3. 후기

https://www.youtube.com/watch?v=DWdFSOehwFI 풀이 참고