[Baekjoon] 1469. 숌 사이 수열 - python

https://www.acmicpc.net/problem/1469

1469번: 숌 사이 수열

문제 정보

문제 유형	난이도	걸린 시간	해결 유무	스스로 구현 성공
백트래킹	골드 5	1h	o	x

설계 방법

백트래킹 알고리즘

각 단계에서 가능한 모든 숫자를 시도하고, 그 선택이 유효한지 확인함

만약 선택이 유효하지 않으면 다음 숫자로 넘어가고, 유효하면 재귀적으로 다음 단계를 탐색함

1. back 함수는 현재 위치(pos)와 각 숫자의 이전 위치(prev)를 인자로 받음
2. pos가 2 * N과 같다면 모든 위치에 대해 값을 할당했다는 뜻이므로 True를 반환
3. 각 단계에서 가능한 모든 숫자 i에 대해 반복문 실행
   • used[i] < 2: 해당 숫자 i가 아직 두 번 사용되지 않았는지 확인
   • (prev[i] != -1 and pos - prev[i] == X[i]+1) or (prev[i] == -1): 이전에 해당 숫자 i가 사용된 적이 있고, 현재 위치와 이전 위치 사이의 거리가 해당 숫자와 일치하거나, 이전에 해당 숫자 i가 사용된 적이 없는 경우
4. 위의 조건들을 만족하는 경우:
   • 수열 S의 현재 위치 pos에 해당하는 값을 i로 설정하고,
   • used 배열에서 i번째 값을 증가시키며,
   • prev 배열에서 마지막으로 등장한 i의 위치를 현재 pos로 업데이트
5. 그 후 재귀적으로 back 함수를 호출하여 다음 단계를 탐색
6. 만약 back 함수 호출 결과 True라면, 정상적인 수열 생성 완료라는 의미니까 True 반환
7. 그렇지 않다면 백트래킹을 수행:
   • 수열 S의 현재 위치 pos값 초기화
   • used 배열에서 i번째 값을 감소시키며,
   • prev 배열에서 마지막으로 등장한 i의 위치 정보 원상 복구
8. 모든 가능성 탐색 후 문제 해결 실패라면 False 반환

• N은 집합 X 안 요소 개수
• X: 집합 X 안 요소들 (여기서는 1부터 N까지의 숫자)
• S: 생성할 수열, 초기에는 모두 0으로 설정
• used: 각 숫자가 몇 번 사용되었는지 저장하는 배열
• prev: 각 숫자가 마지막으로 등장한 위치를 저장하는 배열, 초기에는 모두 -1로 설정

만약 수열 생성이 성공적이라면 생성된 수열을 출력하고, 그렇지 않다면 -1을 출력

코드

def back(pos, prev):
    if pos == 2 * N:
        return True

    for i in range(N):
        if used[i] < 2 and ((prev[i] != -1 and pos - prev[i] == X[i]+1) or (prev[i] == -1)):
            S[pos] = X[i]
            used[i] += 1
            prev_tmp = prev[i]
            prev[i] = pos

            if back(pos + 1, prev):
                return True
            
            # Backtrack
            used[i] -= 1
            S[pos] = 0
            prev[i]=prev_tmp
    return False

N = int(input())
X = sorted(list(map(int, input().split()))) # 만약 여러 개일 경우 사전 순으로 가장 빠른 것을 출력
S=[0]*2*N 
used=[0]*N 
prev=[-1]*N 

if back(0,prev): 
    print(' '.join(map(str,S)))
else:
    print(-1)