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

난이도 : D4

문제번호 : 1267

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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

---

2. 문제풀이

4X4이기 때문에 N=4이고 DFS를 이용해도 무리가 없다고 판단했다. 7자리 숫자를만드는 것인데 중복없이 해야하므로 set을 이용하면 된다. 이제 dfs를 이용하여 숫자를 만들며 완성이 되었다면 set에 집어넣는 과정을 반복한다. 마지막에 set의 길이를 출력하면 만들 수 있는 경우의 수를 모두 만든것이다.

---

3. 소스코드

#D4 2819 격자판의 숫자 이어 붙이기
#상하좌우 이동 리스트
move_list = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
for t in range(1, int(input())+1):
    numlist = [input().split() for _ in range(4)]
    #중복을 없애기 위한 셋
    result = set()
    stack = []
    #각자리마다 만들수 있는 수가 다르므로 각 자리마다 계산
    for i in range(4):
        for j in range(4):
            stack.append((i, j, 0, numlist[i][j]))
            while stack:
                y, x, count, ans = stack.pop()
                #마지막인덱스까지 갔다면 결과 추가하기
                if count >= 6:
                    result.add(ans)
                    continue
                #상하좌우 데이터 넣기
                for d_y, d_x, in move:
                    dy = d_y + y
                    dx = d_x + x
                    if 0 <= dy < 4 and 0 <= dx < 4:
                        stack.append((dy, dx, count+1, ans + numlist[dy][dx]))
                    
    print('#{} {}'.format(t, len(result)))