[SW Expert Academy] 2819. 격자판의 숫자 이어 붙이기

2819. 격자판의 숫자 이어 붙이기

---

문제)

 

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

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

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

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

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

 

[입력]

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

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

 

[출력]

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

 

 

 

 

 

풀이)

from collections import deque
 
def BFS(a, b):
    global answer
 
    queue = deque()
    queue.append([[a, b], str(g[a][b])])
 
    while queue:
        a, b = queue.popleft()
 
        # 정지 조건 (글자수가 7자리가 될 때)
        if len(b) == 7:
            answer.add(b)
 
        else:
            # 글자수가 7자리가 될 때까지 이리저리 돌아다니며 모두 더함
            for i in range(4):
                x = a[0] + di[i]
                y = a[1] + dj[i]
                if -1 < x < 4 and -1 < y < 4:
                    queue.append([[x, y], b + str(g[x][y])])
 
T = int(input())
for _ in range(T):
    g = [list(map(int, input().split())) for i in range(4)]
    di = [0, 0, -1, 1]
    dj = [-1, 1, 0, 0]
 
 
    answer = set()
    for i in range(4):
        for j in range(4):
            BFS(i, j)
 
    print(f"#{_ + 1} {len(answer)}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.