[SWEA][Python] 2819 격자판의 숫자 이어붙이기

set으로 정답이 될수있는 경우를 찾아주면 됩니다.

사실 16칸밖에 되지 않으므로 16자리 bit를 인자로 넘겨주거나 3차원 배열(x, y, bit상태)을 만들어 bit상태와 현재num이 같으면 더 조사하지 않게 가지치기를 할 수 있습니다.

근데 안해도 통과되긴 합니다.

 

def dfs(cnt, x, y, num):
    global answers
    if cnt == 7:
        answers.add(num)
        return
    for dx, dy in delta:
        nx, ny = x + dx, y + dy
        if 0 <= nx < 4 and 0 <= ny < 4:
            next_num = num + matrix[nx][ny]
            if cnt == 6 and next_num in answers:
                continue
            dfs(cnt + 1, nx, ny, next_num)


for test in range(1, int(input()) + 1):
    matrix = [list(input().split()) for __ in range(4)]
    answers = set()

    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    for i in range(4):
        for j in range(4):
            dfs(1, i, j, matrix[i][j])
    print(f'#{test} {len(answers)}')