[SWEA] D4 2819 격자판의 숫자 이어 붙이기 (Python)

출처

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

문제

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

 

풀이

격자판 위치마다 dfs를 통해 완전 탐색을 하여 해결함. 격자판의 크기 4 x 4로 데이터 자체가 작아서 DFS로 돌려도 충분

최초 격자판 생성때 숫자를 int형이 아닌 str형으로 받아 +로 붙이는게 가능하도록 만들었으며 중복값 제거를 위해 마지막에 결과값이 저장된 배열을 set형으로 만들어 중복을 제거하였다.

 

코드

def dfs(idx,row,col,num):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    num += mapp[row][col]
    if idx == 6: # 6번 이동한 결과 값 result 배열에 추가
        result.append(num)
        return
    for i in range(4):
        if 0 <= row+dx[i] < 4 and 0 <= col+dy[i] < 4: # 벽 체크
            dfs(idx+1,row+dx[i],col+dy[i],num)
 
T = int(input())
for t in range(T):
    mapp = [list(map(str,input().split())) for _ in range(4)]
    result = [] # 결과값 저장 될 배열
    for x in range(4):
        for y in range(4):
            dfs(0,x,y,"")
 
    answer = set(result) # 중복 제거를 위해 set 사용
    print('#{} {}'.format(t+1,len(answer)))