[Python, 파이썬] SWEA 2819. 격자판의 숫자 이어 붙이기

 

4x4 크기의 격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 문제.

 

 

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

 

만들 수 있는 서로 다른 7자리 숫자의 개수를 구하는 문제.

 

 

 

[코드]

---

def DFS(i, j, num, length):
 
    if not (0 <= i < N and 0 <= j < N): # 0<= x <N 사이에 있지 않을때
        return
 
    if length == 0: # 7자리 수가 되면
        com.add(num) # 조합 저장
        return
 
    DFS(i+1, j, num+A[i][j], length-1) # 아래로 이동
    DFS(i, j+1, num+A[i][j], length-1) # 오른쪽으로 이동
    DFS(i, j-1, num+A[i][j], length-1) # 왼쪽으로 이동
    DFS(i-1, j, num+A[i][j], length-1) # 위로 이동
     
T = int(input()) # 테스트케이스 수 T
 
for test_case in range(1, T+1):

    N = 4 # 4개의 격자판
    A = [] # 수열 A
 
    # 수열 입력받기
    for i in range(4):
        A.append(list(input().split()))
     
    # 탐색 시작
    com = set()

    for i in range(4):
        for j in range(4):
            DFS(i, j, '', 7) # 가장 짧은 경로 계산
             
    print("#%d %d" %(test_case, len(com))) 

 

 

 

 

[문제풀이]

---

전형적인 DFS를 사용해 푸는 문제.

 

4x4 격자판 안에서 동서남북으로 이동하면서 7자리 수를 이어붙인다.

DFS(i+1, j, num+A[i][j], length-1) # 아래로 이동
DFS(i, j+1, num+A[i][j], length-1) # 오른쪽으로 이동
DFS(i, j-1, num+A[i][j], length-1) # 왼쪽으로 이동
DFS(i-1, j, num+A[i][j], length-1) # 위로 이동

 

그리고 이어붙인 개수가 7개가 되면 set()에 추가해 중복을 걸러내면 끝!

그 후 set의 개수를 구하면 그게 바로 4x4 격자판 안에서 만들 수 있는 서로 다른 7자리 숫자의 개수다.