[백준] 1941 소문난 칠공주 python

www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

matrix = [input() for _ in range(5)]
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
result_set = set()


def backtrack(arr, index=0, S=0, Y=0):
    tmp = arr
    if Y > 3:
        return
    if index == 6:
        arr.sort()
        result_set.add(tuple(arr))
    else:
        adjacents = []
        for node in range(len(arr)):
            for i in range(4):
                dx = arr[node][0] + delta[i][0]
                dy = arr[node][1] + delta[i][1]
                if 0 > dx or 5 <= dx or 0 > dy or 5 <= dy: continue
                if (dx, dy) in arr: continue
                adjacents.append((dx,dy))
        for adjacent in adjacents:
            nx = adjacent[0]
            ny = adjacent[1]
            if matrix[nx][ny] == 'S':
                backtrack(arr+[(nx,ny)], index+1, S+1, Y)
            else:
                backtrack(arr+[(nx,ny)], index+1, S, Y+1)

for i in range(5):
    for j in range(5):
        if matrix[i][j] == 'S':
            backtrack([(i, j)], index=0, S=1)

print(len(result_set))

백트래킹으로 모든 조합을 만들었다.

조합을 만들때 이미 고른 원소에서 인접된 칸의 원소들을 확인하고, 그 원소들을 넣는 방식으로 진행하였다.

완전한 브루트포스로 하면 시간초과가 날것이라 생각해서 Y(임도연파)가 세명을 초과하는 경우에는 가지치기로 쳐냈다.

예제 기준으로 94개의 조합이 나오는데 이때 arr 원소는 같은데 순서가 뒤죽박죽이면 다른 원소인 것으로 판단되었다.

그래서 정렬하여 순서를 맞추고 set으로 중복을 제거하니 제대로 된 값이 나왔다. 

---

다른 사람이 푼 코드중에 속도가 빠른 것을 확인했는데 코드가 얼추 비슷하다.

나랑 다른점은 arr를 직접 사용하지 않는다는점이다.