[python] SWEA - 2819. 격자판의 숫자 이어 붙이기

문제 해결

1. D4 | 재귀를 이용한 DFS

2. 시작점을 하나 선택하고 dfs함수 실행

3. 선택한점에서 4방향 탐색(인덱스 범위 이내) 후 해당 지점의 숫자를 더해가며 dfs재귀함수실행

4. 숫자의 길이가 7이 되면 함수를 종료하고, 결과 리스트에 넣어준다.(여기서는 중복을 피하기위해 set을 사용)

5. 모든 경우의 수를 탐색 후 답을 출력

 

💨 D4라고 하기엔 조금 쉬운 문제였다.

 

소스 코드

 def dfs(number, x, y):
    # 길이가 7이 되면 result에 값을 추가하고 break
    if len(number) == 7:
        result.add(number)
        return

    # 상하좌우 4방향을 탐색
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        # 리스트의 범위를 벗어나지 않으면
        if 0 <= nx < 4 and 0 <= ny < 4:
            # number에 값을 붙여주고 다음 지점으로 이동하여 재귀탐색
            dfs(number + maps[nx][ny], nx, ny)

    return


dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for tc in range(1, 1 + int(input())):
    maps = [input().split() for _ in range(4)]

    # 중복이 없기 때문에 set을 사용했다.
    result = set()
    # 시작 지점을 선택
    for i in range(4):
        for j in range(4):
            dfs('', i, j)
    print('#{} {}'.format(tc, len(result)))

 

출처: SW Expert Academy

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

SW Expert Academy

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다. 격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다. 단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다. 격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다. [출력] 각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.