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

1. 문제 이해

4x4 격자판에 0부터 9까지의 숫자가 있다.
임의의 위치에서 시작하여 4방향으로 6번 이동하며 7자리 숫자를 만든다.
만들 수 있는 서로 다른 일곱 자릿수 들의 개수는?

입력값:
테스트 케이스 T
각 방의 값 (4 줄에 걸쳐, ' '으로 나누어져 있다.)

유의해야 할 점:
왔던 곳 다시 갈 수 있다.
0으로 시작하는 수도 만들 수 있다.

출력 값:
#테스트 케이스, 만들 수 있는 수의 개수

 

2. 문제 풀이 법

사용한 방법: DFS
1. 4x4의 칸들로부터 시작한다.
2. 현재 자리가 7일 경우 멈추고 결괏값을 저장한다.

인자 : [현재 위치], 자릿수, 현재까지 만들어진 수

 

3. 어려웠던 점

dfs를 사용할 때 종료 조건이 있고 return을 해줘야 한다는 점을 다시 한번 깨달았다.

1. 처음부터 result를 set으로 준 경우

T = int(input())
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def search(pos,k,t_res):
    if k == 7:
        results.add(t_res)
        return
    x,y = pos
    for dir in range(4):
        temp_x = x + dx[dir]
        temp_y = y + dy[dir]
        if (0<= temp_x < 4) and ( 0<=temp_y <4 ):
            search([temp_x,temp_y],k+1,t_res+str(board[temp_y][temp_x]))


for tc in range(1,T+1):
    board = [list(map(int,input().split()))for _ in range(4)]
    results = set()
    for i in range(4):
        for j in range(4):
            search([i,j],0,'')

    print('#{} {}'.format(tc, len(results)))

2. result를 list로 두고 set으로 바꿨을 때

T = int(input())
dx=[1,-1,0,0]
dy=[0,0,1,-1]
 
def search(pos,k,t_res):
    if k == 7:
        results.add(t_res)
        return
    x,y = pos
    for dir in range(4):
        temp_x = x + dx[dir]
        temp_y = y + dy[dir]
        if (0<= temp_x < 4) and ( 0<=temp_y <4 ):
            search([temp_x,temp_y],k+1,t_res+str(board[temp_y][temp_x]))
 
 
for tc in range(1,T+1):
    board = [list(map(int,input().split()))for _ in range(4)]
    results = []
    for i in range(4):
        for j in range(4):
            search([i,j],0,'')
 
    print('#{} {}'.format(tc, len(set(results))))

 

4. 배운 점

중복을 제거하는 문제의 경우 처음부터 set에 add 하는 것이 더 빠르다.

1번 코드 결과

2번 코드 결과

혹시 더 좋은 풀이나 조언이 있다면 댓글 달아주세요.