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

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

계획

가능한 모든 경우를 확인해야 하므로 격자판 위의 모든 지점에서 dfs 함수를 호출한다. 중복 방문이 가능하므로 visited 배열은 만들지 않았고, 같은 숫자가 나올 경우 한 번만 세야 하므로 완성된 7자리 숫자는 따로 검사하지 않고 모두 set에 문자열로 담아주었다.

코드

delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def is_valid(x, y):
    return 0 <= x < 4 and 0 <= y < 4

def make_num(x, y, num):
    if len(num) == 7:
        numbers.add(num)
        return
    for d in range(4):
        tx = x + delta[d][0]
        ty = y + delta[d][1]
        if is_valid(tx, ty):
            make_num(tx, ty, num + arr[tx][ty])

T = int(input())
for tc in range(1, T+1):
    arr = [input().split() for _ in range(4)]
    numbers = set()

    for i in range(4):
        for j in range(4):
            make_num(i, j, arr[i][j])

    print('#{} {}'.format(tc, len(numbers)))

풀이방법

계획한대로 풀었으나 각 지점에서 처음 함수를 호출할 때 arr[i][j]를 num에 담고 시작하도록 수정했다. 해당 위치에서 함수를 호출했다는 건 해당 위치를 방문한 것이나 마찬가지이므로 이렇게 시작하면 나머지 6개의 숫자만 담으면 돼서 실행시간을 줄일 수 있었다.