[Python] 백준 1941번: 소문난 칠공주

이 문제는 dfs를 이용해서 중복없는 조합을 모두 구하고,
bfs를 응용해서 인접한 조합인지 여부를 확인하여 풀 수 있습니다.

1. (0,0), (0,1), ... , (4,4)의 크기가 25인 리스트를 정의한 후, 이들 중 7개를 중복없이 선택하는 조합을 구함
2. 조합에서 'S'의 수가 4개 이상이고, 위치가 인접해있으면 ans +=1
3. ans를 출력

중복없는 조합은 dfs를 사용한 백트래킹 방식으로 쉽게 구할 수 있습니다.
이차원 배열을 1번처럼 변형하면 일차원 배열에서 사용하던 백트래킹 형식을 그대로 사용할 수 있습니다.

이제 bfs를 사용하여 인접 여부를 확인하는 알고리즘이 메인인데요,
dfs를 사용해서 스택 s에 7개의 원소를 구했을 때,

1. s[0]을 q에 넣은 후, s에서 s[0]을 제거
2. q에 있는 원소를 돌면서 bfs 시작
3. (x, y)를 기준으로 인접한 (nx, ny)에 대해 s에 들어있는 (nx, ny)가 있다면
   (nx, ny)를 q에 넣은 후, s에서 (nx, ny)를 제거
4. q가 empty할 때까지 반복
5. s에 원소가 남아있으면 False, 없으면 True

q에 넣은 원소는 이미 확인한 원소이므로, s에서 제거해줍니다.
이 과정은 방문 체크의 역할을 하게 됩니다.

만약 s에 들어있는 좌표가 모두 인접하여 한 덩어리였다면,
각각의 좌표가 누군가의 (nx, ny)로 확인되어 s에서 제거되었을 것입니다.
따라서 s에서 제거되지 않은 좌표가 있다면, s[0] 좌표와 인접하지 않은 좌표일 것이므로 False가 됩니다.

from collections import deque

board = [list(input()) for _ in range(5)]
idx = [(i, j) for i in range(5) for j in range(5)]
s = []
n = []
ans = 0


def is_available(s):
	l = [i for i in s]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    q = deque([l[0]])
    l.remove(l[0])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (nx, ny) in l:
                q.append((nx, ny))
                l.remove((nx, ny))
    if len(l) == 0:
        return True
    return False


def dfs(depth):
    global ans
    if len(s) == 7:
        if n.count('S') >= 4 and is_available(s):
            ans += 1
        return
    for i in range(depth, 25):
        x, y = idx[i]
        s.append((x, y))
        n.append(board[x][y])
        dfs(i + 1)
        s.pop()
        n.pop()


dfs(0)
print(ans)

부가적으로, 리스트를 복사할 때 deepcopy를 사용하면 시간초과가 발생할 확률이 높으므로
l = [i for i in s]를 사용해주는 것이 좋습니다.