[Python] 2819. 격자판의 숫자 이어 붙이기 - Python

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

SW Expert Academy

< 📝 문제 >
4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫

 

자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.

격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.

< ❓ 생각 >

< 💻 코드 >

1. 입력값 str

def check(idx,r,c,num):
    num += arr[r][c]
    d =[(0,1),(0,-1),(1,0),(-1,0)]
    if idx == 6: # 6번의 이동
        result.append(num)
        return num
    for i in range(4):
        if 0<=r+d[i][0]<4 and 0<=c+d[i][1]<4: # 범위 내에 있어야 함
            check(idx+1,r+d[i][0],c+d[i][1],num)

T = int(input()) # 테스트 케이스의 수
for tc in range(1,T+1):
    arr = [input().split() for _ in range(4)] # 4*4 격자판, 뒤에 더 할꺼니깐 숫자 말고 문자
    result = []
    for r in range(4):
        for c in range(4):
            check(0,r,c,'')
    result_set = set(result) # 서로 다른 일곱자리 수들의 개수 구하기
    print(f'#{tc} {len(result_set)}')

2. 입력값 int

# n : idx
def DFS(n,ci,cj,num):
    if n ==7:
        sset.add(num)
        return
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        ni,nj = ci+di,cj+dj
        if 0<=ni<4 and 0<=nj<4:
            DFS(n+1,ni,nj,num*10+arr[ni][nj])

# 테스트 케이스의 수
T = int(input())
for tc in range(1,T+1):
    # 4*4 격자판
    arr = [list(map(int,input().split())) for _ in range(4)]
    sset = set()
    for i in range(4):
        for j in range(4):
            DFS(0,i,j,0)
    print(f'#{tc} {len(sset)}')

< ❗ >

중복을 해결하기 위해 list를 set으로 변경!!!

set은 중복X, 순서X