격자판의 숫자 이어 붙이기 Python (SW Expert Academy)

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

SW Expert Academy

 

1. 문제 설명

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

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

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

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

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


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.


[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.

 

2. 코드

숫자의 조합이 어떻게 나올지 모르기 때문에 완전 탐색을 해야한다고 생각하였습니다. 방향을 움직이는 것도 인덱스 내부라면 모두 움직이도록 작성하였습니다.

배열을 만들면서 지나왔던 자리도 다시 갈 수 있기 때문에 추가적으로 해준 것은 없습니다.

추가적으로 입력을 받을 때 7자리 숫자를 붙이면 만드는 것이 목표였기 때문에 str로 그대로 배열을 만들었습니다.

 

아래가 작성한 코드입니다.

# 배열의 인덱스 내부임을 확인하기 위한 함수
def wall(x, y):
    if x > N-1 or x < 0 or y > N-1 or y < 0:
        return False
    return True
 
# 숫자를 생성하기 위한 함수
def num_make(s, x, y, r):
    # 일곱 자리 수가 완성되었을 때
    if s == 6:
        # 결과값에 들어가 있지 않다면 추가
        if r not in result:
            result.append(r)
    else:
        # 4가지 방향으로 가기 위한 반복문
        for d in range(4):
            if wall(x+dx[d], y+dy[d]):
                num_make(s+1, x+dx[d], y+dy[d], r+arr[y+dy[d]][x+dx[d]])
 
T = int(input())
for t in range(1, T+1):
    N = 4
    # str로 사용하는 것이 편해 그대로 받아옴
    arr = [list(input().split()) for _ in range(N)]
    # 우, 좌, 하, 상
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    result = []
    # 배열의 모든 원소를 방문하기 위한 반복문
    for j in range(N):
        for i in range(N):
            start_y = j
            start_x = i
            num_make(0, start_x, start_y, arr[start_y][start_x])
    
    print('#{} {}'.format(t, len(result)))