SW Expert Academy 2819 격자판의 숫자 이어 붙이기

문제 링크: https://swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV7I5fgqEogDFAXB

SW Expert Academy

단순히 DFS로 모든 격자판 위치에서 7자리 숫자를 만들어서 중복을 제거하면 되는 문제였다. 처음에는 시간 초과를 하였는데, w7을 list로 만들어서 7자리 숫자가 이미 w7에 있는지 확인하였는데, w7을 set으로 선언하고 추가하는 식으로 하였더니 시간 초과가 뜨지 않고 통화하였다. 나의 풀이는 아래와 같다.

def solution(map1,x,y,sub):
    global w7
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    if len(sub)==7:
        w7.add(sub)
        return
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<4 and -1<ny<4:
            solution(map1,nx,ny,sub+map1[nx][ny])   
t=int(input())
for test in range(1,t+1):
    w7=set()
    map1=[]
    for _ in range(4):
        map1.append(input().split())
    for i in range(4):
        for j in range(4):
            solution(map1,i,j,'')
    answer=len(w7)
    print('#{} {}'.format(test,answer))