[SWEA] 격자판의 숫자 이어붙이기 #파이썬 #DFS

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

SW Expert Academy

문제요약
임의의 위치에서 시작해서 6번의 이동(인접 영역, 즉 상하좌우)을 하면서 숫자를 이어붙이면 7자리 숫자가 된다.
나올 수 있는 숫자 종류(개수)를 출력하는 프로그램을 작성

아이디어
1. 모든 좌표를 순회한다.
2. 매좌표마다 깊이우선 탐색(깊이는 6으로)으로 숫자를 생성해 리스트에 담는다.
2-1. 이 때, 이미 들어가 있는 숫자는 리스트에 담지 않고 pass.
3. 마지막에 리스트에 담긴 원소들의 개수를 센다.

 

>>소스코드1 (메모리 66,408 kb/ 실행시간 4,843 ms/결과 PASS)

 

def dfs(i, j, result, depth):
    global ans_list
    if depth == 6:
        if result not in ans_list:
            ans_list.append(result)
            return
        return
 
    for k in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        ni = i + k[0]
        nj = j + k[1]
        if ni < 0 or ni >= 4 or nj < 0 or nj >= 4:
            continue
        else:
            result += str(matrix[ni][nj])
            dfs(ni, nj, result, depth + 1)
            result = result[:-1]
 
T = int(input())
for tc in range(1,T+1):
    print(f'#{tc}',end=" ")
    matrix = [list(map(int,input().split())) for _ in range(4)]
    ans_list = []
 
    for i in range(4):
        for j in range(4):
            dfs(i,j,str(matrix[i][j]),0)
 
    print(len(ans_list))

 

>>소스코드2(메모리 67,716 kb/실행시간 332 ms/결과 PASS)

 

def dfs(i, j, result, depth):
    global ans_set
    if depth == 6:
        ans_set.add(result)
        return
 
    for k in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        ni = i + k[0]
        nj = j + k[1]
        if ni < 0 or ni >= 4 or nj < 0 or nj >= 4:
            continue
        else:
            result += str(matrix[ni][nj])
            dfs(ni, nj, result, depth + 1)
            result = result[:-1]
 
T = int(input())
for tc in range(1,T+1):
    print(f'#{tc}',end=" ")
    matrix = [list(map(int,input().split())) for _ in range(4)]
    ans_set = set()
 
    for i in range(4):
        for j in range(4):
            dfs(i,j,str(matrix[i][j]),0)
 
    print(len(ans_set))

 

처음에 별 생각없이 리스트에 담고, 중복을 제거하는 로직을 따로 구현해서 답을 도출했는데, 혹시나 해서 list를 set으로 바꿔봤더니 시간이 어마하게 줄었다. 중복제거할 땐, set을 쓰자,,