[SWEA] 격자판의 숫자 이어 붙이기 (python)

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

SW Expert Academy

4*4 크기의 격자판을 상하좌우로 움직이면서 이어 붙였을 때 (중복 가능) 찾을 수 있는 7자리 수 중 서로 다른 개수를 찾는 문제

백트래킹을 활용하여 풀 수 있다.

⚙️내가 푼 정답 코드

def find(y,x,num):
    if len(num) == 7: #길이가 7이야
        result.append(num) # 리스트에 넣자
        return # 끝
    for dy, dx in move : # 움직이자
        ny, nx = y + dy, x + dx
        if 0<= ny < 4 and 0 <= nx < 4: 
            find(ny,nx,num+board[ny][nx]) #번호 붙여가면서 찾아보자

T = int(input())
for case in range(1,T+1): 
    board = [list(input().split()) for _ in range(4)]
    move = [[1,0],[0,1],[-1,0],[0,-1]] # 윰작암
    result = [] # 저장
    for i in range(4): # 시작
        for j in range(4): #위치
            find(i,j,board[i][j]) # 지정
    print(f'#{case} {len(set(result))}')

📌 문제 접근 포인트

1. 4*4의 격자판을 움직이면서 값을 찾아야 한다. 범위 내에서 찾아야 하는 조건을 생각해주면 쉽게 접근할 수 있다.
2. 칸마다 최대로 만들어지는 모양의 갯수가 다르므로, 모든 칸에서 백트래킹으로 탐색해줄 필요가 있다.
3. 백트래킹으로 탐색하면서 숫자를 더해주고, 갯수를 모아서 중복을 제거해주면 끝!
4. 다만 중복을 제거하겠다고 재귀 안에 if num not in result로 조건을 넣어버리면 연산이 굉장히 늘어나 시간이 오래 걸리게 될 수 있으므로, set()함수를 이용해서 중복을 제거해주자.