SWEA 2819번: 격자판의 숫자 이어 붙이기 (D4) - Python 풀이

문제 설명

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

sample_input.txt

출력

#1 23

sample_output.txt

문제 요약) 4*4 격자판에서 상하좌우 이동만 가능하고 한 번 거쳤던 격자칸을 다시 거쳐도 될 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구해라.

풀이 과정

D4라고 하지만 쉬운 문제입니다. 격자판이 4*4 고정으로 입력 크기가 작아서 가능한 모든 케이스를 탐색하면 됩니다.

상하좌우로 이동하면서 7자리 숫자를 찾아야 하니까 재귀 호출 스택을 통해 깊이 우선 탐색을 구현했습니다.

1. 상하좌우 방향 벡터를 만들어서 재귀적으로 탐색한다.
2. 7자리 숫자니까 depth가 7일 때 종료한다.
3. 한 번 거쳤던 격자칸을 다시 거쳐도 되기 때문에 visited 같은 변수는 안 써도 된다.
4. 찾은 7자리 숫자들을 set 자료형에 저장해서 중복을 피한다.

정답 코드

T = int(input())
for test_case in range(1, T + 1):
    # 만들 수 있는 케이스를 중복 없이 모두 구하기 위해 set 자료형 사용
    answers = set()
    # 4*4 격자판
    grid = [[] for _ in range(4)]
    # 격자판 입력
    for i in range(4):
        grid[i] = list(map(int, input().split()))
        
    # 상하좌우 이동 벡터
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
	  
    # 재귀 방식으로 탐색
    def dfs(depth, x, y, number):
        # depth가 7이면 (= 7개의 숫자를 찾았다)
        if depth == 7:
            # 7개 숫자를 set 자료형에 추가
            answers.add(int(number))
            # 재귀 종료
            return
        # 격자판의 (x,y)의 값을 문자로 변환하고 number의 뒤에 이어붙인다
        number += str(grid[x][y])
        # 상하좌우 네 가지 방향 값을 확인
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 이동할 좌표가 그리드 내의 좌표인지 확인
            if 0 <= nx < 4 and 0 <= ny < 4:
                # 재귀로 depth 1 증가시켜서 (nx, ny) 좌표로 이동
                dfs(depth+1, nx, ny, number)
 
    # 탐색의 시작점을 4*4 격자판의 모든 좌표로 설정
    for x in range(4):
        for y in range(4):
            # (x,y) 시작점에서 재귀적으로 탐색 시작
            dfs(0, x, y, "")
    # set 자료형의 길이를 출력
    print("#%d %d" % (test_case, len(answers)))

이상입니다.