Python으로 푸는 SW Expert Academy 2819. 격자판의 숫자 이어 붙이기

 SW Expert Academy 2819. <격자판의 숫자 이어 붙이기> 문제는 

격자판의 원소를 총 6번 이동하면서, 각 칸에 적힌 숫자를 차례대로 이어 붙여

 만들 수 있는 7자리의 수의 갯수를 구하여야 한다.

삼성 SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제 조건

격자판을 벗어나선 안된다.

한번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 수를 만들 수도 있다.

+ 제자리 걸음을 해선 안된다.

+ 만들어진 숫자가 중복 되어선 안된다.

문제 풀이

완전 탐색 방법으로 문제를 풀어야 한다. 격자판의 16개의 원소 각각을 시작점으로 하여 6번을 이동했을 때 나올 수 있는 모든 경우를 탐색해야 한다.

단, 나올 수 있는 7자리 숫자의 모든 경우의 수를 탐색하면서도 그게 기존에 나온 숫자인지도 확인해야 한다. python은 집합(set()) 컨테이너를 활용한다면 쉽게 중복을 제거할 수 있다.

재귀를 잘 활용하면 문제는 금방 풀 수 있는데, 다른 사람들이 푸는 방법대로 전역 변수를 설정해서 문제를 풀어보았더니 테스트 케이스마다 초기화 해주는 것을 까먹어서 에러가 자꾸만 났다. 

이 부분만 주의하면 될것 같다.

파이썬 코드

number_set = set()
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
string = ''
pos_list = []
 
def explore(start, count):
    global string
    global before_pos
    global pos_list
 
    x, y = start
    # 문자열 완성
    if count == 0:
        number_set.add(string)
        return
 
    for i in range(4):
        temp_x = x + dx[i]
        temp_y = y + dy[i]
 
        if temp_x >= 0 and temp_y >= 0 and temp_x < 4 and temp_y < 4:
            string += str(array[temp_x][temp_y])
            pos_list.append((temp_x,temp_y))
            # 다음 경로 설정
            explore((temp_x, temp_y), count - 1)
            # 맨 마지막 지점을 방문하지 않은 것으로 변경
            string = string[:-1]
            pos_list.pop(-1) # 맨 마지막 경로를 제외
 
def solve():
    global string
    global pos_list
    # 시작 지점 설정
    for i in range(0, 16):
        pos_list = []
        string += str(array[i // 4][i % 4])
        pos_list.append((i//4, i%4))
        explore((i//4, i%4), 6)
        string = ''
    return len(number_set)
 
if __name__ == "__main__":
    t = int(input())
    for tc in range(t):
        # 초기화
        array = []
        number_set = set()
        pos_list = []
        string = ''
 
        for j in range(4):
            array.append(list(map(int, input().strip().split())))
        result = solve()
        print('#{0} {1}'.format(tc + 1, result))

#SW Expert Academy 2819. 격자판의 숫자 이어 붙이기 #sw expert 2819 격자판의 숫자 이어 붙이기 #python 2819 격자판의 숫자 이어 붙이기 #2819 격자판의 숫자 이어 붙이기 python #sw expert 2819 #python 2819 격자판