[백준 1469번] 숌 사이 수열

1469번: 숌 사이 수열

import sys
sys.setrecursionlimit(10**7)
n = int(input())

# X의 크기는 8보다 작거나 같은 자연수
# X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수이다.

# 사전 순으로 가장 빠른 것

x = sorted(list(map(int,input().split())))

s = [-1 for _ in range(n*2)]
visited = [False for _ in range(17)]

def dfs(index):

    if index == n*2:
        for i in s:
            print(i,end=" ")
        exit(0)

    if s[index] != -1: # 이미 원소가 있다면 다음 인덱스 체크
        dfs(index+1)
        return

    for i in range(n):
        num = x[i] # 원소 값
        next_index = index + num + 1 # 현재 인덱스 + 원소 값 + 1
        if not visited[num]: # 해당 원소가 아직 사용되지 않았다면
            if 0<= next_index < n*2 and s[next_index] == -1:
                s[index] = num
                s[next_index] = num
                visited[num] = True
                dfs(index+1)
                s[index] = -1
                s[next_index] = -1
                visited[num] = False

dfs(0)

print(-1)

이번 문제는 X에 들어 있는 n개의 모든 원소가 2개씩 존재하고, 해당 원소와 다른 하나의 원소 사이에는 그 원소의 값 만큼 거리가 떨어져있는 수열을 구하는 문제이다.

 

처음에 이 문제를 풀 때 완전 탐색으로 풀려고 DFS를 사용했는데, X의 개수가 8개가 되었을 때 최대 16! 의 경우의 수가 발생하여 시간초과가 발생했다.

백트래킹 : 해가 될 가능성이 있는지 판단하고 그렇지 않으면 해당 경로를 탐색하는 것을 하지 않고 가지치기 하는 알고리즘

이 문제를 시간초과 없이 풀기 위해서는 백트래킹을 사용하여 경우의 수를 줄여야한다.(사실 필자도 백트래킹을 사용하긴 했으나 가지치기 방식이 잘못된 것 같음)

 

따라서 첫 인덱스부터 하나씩 n개의 원소 중 아직 사용하지 않은 원소를 저장하고, (현재 인덱스 + 원소 값 + 1) 자리에도 원소를 저장해준다.

 

여기서 중요한 점은 바로 visited 를 활용한 가지치기이다. visited 리스트는 현재까지 사용된 원소를 추적하고, 이미 사용된 원소는 다시 사용하지 않도록 제한한다.

(이렇게 하면 같은 원소가 중복해서 사용되거나 이미 사용된 원소가 다시 사용되는 것을 방지하고, 효율적인 가지치기가 이루어진다.)

 

배운 점 및 느낀 점

1. 답을 찾는 즉시 프로그램을 종료하고 싶다면 exit() 사용할 것
2. Recursion error를 방지하기 위해서는 sys.setrecursionlimit()을 사용할 것
3. 수열의 값을 채우는 문제는 인덱스로 차근차근 탐색하자
4. 완전 탐색을 사용할 때는 최대한 depth나 index를 하나씩 더해가며 풀자