0305_SW 2819번 : 숫자 이어 붙이기

출처 : 소프트웨어 엑스퍼트 아카데미 2819번 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE

SW Expert Academy

 

#1차 시도 : DFS 재귀함수 이용해 델타 값으로 이동하며 7자리 수 만들기

 

- FOR문으로 2차원 배열의 모든 점을 시작점으로 재귀함수 시작하기

- 처음에는 배열 입력 받을 때 int값으로 받았지만, 7자리 수들을 결과 리스트 안에 하나씩 넣어주기 위해 나중에 str으로 변환했음 ( 처음부터 스트링으로 받는 것도 방법)

- 결과 리스트 안에 중복된 7자리 수를 없애기 위해, FOR문 not in으로 중복 값을 결과 리스트에 넣지 않을 수도 있지만 set()함수를 통해 중복값을 없애는 게 효율적

- 다만 7자리 숫자를 만들기 위해 재귀를 여러번 돌리기 때문에 시간은 비효율적

 

def dfs(idx,r,c,res):
    res += str(arr[r][c])
    if idx == 6:
        n_lst.append(res)
        return
    for i in range(4):
        if 0 <= r+dx[i] < 4 and 0 <= c+dy[i] < 4:
            dfs(idx+1, r+dx[i], c+dy[i], res)
 
for t in range(1,int(input())+1):
    arr = [list(map(int,input().split())) for _ in range(4)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    n_lst = []
    for i in range(4):
        for j in range(4):
            s_x = i
            s_y = j
            dfs(0,s_x,s_y,'')
    result = set(n_lst)
    print(f'#{t} {len(result)}'함

for t in range(1,int(input())+1):
    #배열에서 int가 아닌 str 형태로 입력받기
    arr = [input().split() for _ in range(4)]
    result = set()
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
 
    for i in range(4):
        for j in range(4):
            stack = [(i,j,0,arr[i][j])]
            while stack:
                x, y, cnt, num = stack.pop()
                if cnt == 6:
                    result.add(num)
                else:
                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]
                        if 0<= nx < 4 and 0<= ny < 4:
                            stack.append((nx,ny,cnt+1,arr[nx][ny]+num))
    print('#{} {}'.format(t,len(result)))