[SWEA][D4][#02819] 격자판의 숫자 이어 붙이기

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

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

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

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

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

입력

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

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

출력

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

예제

입력

1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1

출력

#1 23

My Sol A : 숫자 변환

def dfs(ni, nj, now, limit):
    global stack
    if now == limit:
        global dictA
        sumV = 0
        for i in range(7):
            sumV += stack[i]*(10**(6-i))
        dictA[sumV] = 1
        return

    didj = [(-1,0),(1,0),(0,1),(0,-1)]
    for di, dj in didj:
        si, sj = ni+di, nj+dj
        if not (0<=si<4 and 0<=sj<4): continue
        stack.append(mat[si][sj])
        dfs(si, sj, now+1, limit)
        stack.pop()


T = int(input())
for tc in range(1, T+1):
    mat = [list(map(int, input().split())) for _ in range(4)]
    dictA = {}
    for i in range(4):
        for j in range(4):
            stack = [mat[i][j]]
            dfs(i, j, 0, 7)

    print(f'#{tc} {len(dictA.keys())}')

My Sol B : 문자 사용

def dfs(ni, nj, now, txt):
    if now == 7:
        global dictA
        dictA[txt] = 1
        return

    for di, dj in didj:
        si, sj = ni+di, nj+dj
        if not (0<=si<4 and 0<=sj<4): continue
        dfs(si, sj, now+1, txt+mat[si][sj])

didj = [(-1,0),(1,0),(0,1),(0,-1)]
T = int(input())
for tc in range(1, T+1):
    mat = [input().split() for _ in range(4)]
    dictA = {}
    for i in range(4):
        for j in range(4):
            dfs(i, j, 0, '')

    print(f'#{tc} {len(dictA.keys())}')

완전탐색과 dfs를 이용했다. 16칸의 모든 칸마다 시작하는 dfs 함수를 작성한다. 이 함수는 상하좌우마다 조회하는데, 범위 내라면 stack에 해당 좌표의 값을 넣는다. 이렇게 7개의 수가 stack에 쌓이면 이를 for문을 이용해 곱해주어 dictionary의 key로 사용한다. 그러면 중복을 제외할 수 있다.

이후 모든 칸을 완전탐색하게 되면, dictionary의 key의 개수를 계산해 출력하면 되겠다. 다소 완전탐색의 효율이 많이 떨어지지만, 4x4의 크기이기 때문에 시간적으로나 메모리 초과가 나지 않은 것 같다. 백트래킹의 가지치기나 DP에서 더 좋은 풀이를 착안할 수 있을 것이라고 생각하는데 조금 더 고민해볼 필요가 있는 풀이였다.

결과

PASS