[파이썬 | SW Expert Academy] 격자판의 숫자 이어 붙이기

[문제]

 

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

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

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

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

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


[입력]

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

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


[출력]

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

 

[풀이]

 

DFS를 사용해서 7번째까지 탐색한다. 따로 중복 방문 조건이 없으므로, depth 말고는 조건을 두지 않아도 된다.

 

따라서 depth가 7이면 return 하는 조건으로 재귀 탐색을 하고, 그 외에 조건은 i, j가 0이상 4미만 이어야 한다.

 

중복을 검사하는 알고리즘은 파이썬의 경우에는 container를 set로 설정하면 손쉽게 중복을 처리할 수 있다.

 

 

d = [[-1, 0],[1, 0],[0, -1],[0, 1]]
 
def DFS(maps, i, j, depth, num):
    if depth == 7:
        ans.add(num)
        return
    for idx in range(4):
        nextI, nextJ = i+d[idx][0], j+d[idx][1]
        if nextI >= 0 and nextI < 4 and nextJ >= 0 and nextJ < 4:
            DFS(maps, nextI, nextJ, depth+1, num + str(maps[i][j]))
 
def solve(idx):
    maps = []
    for i in range(4):
        maps.append(list(map(int, input().split())))
    for i in range(4):
        for j in range(4):
            DFS(maps, i, j, 0, '')
    print('#%d ' % idx, end='')
    print(len(ans))
 
T = int(input())
 
for i in range(1, T+1):
    ans = set()
    solve(i)