문제 링크: https://www.acmicpc.net/problem/15918

Thumbnail: Photo by Miikka Luotio (Unsplash)

오늘도 즐거운(?) 백트래킹입니다.

풀이

랭퍼든 수열?

문제에서 언급한 랭퍼든 수열은 다음의 규칙을 가집니다.

• 1 이상 n 이하의 자연수가 각각 두 개씩 들어 있다.
• 두 개의 n 사이에는 정확히 n개의 수가 있다.

단, 문제에서는 두 위치 \(X\)와 \(Y\)에 같은 수가 위치해야 한다고 조건을 걸어두었습니다. 이때, 위 랭퍼든 수열의 규칙을 생각해보면 \(X\)와 \(Y\)에 들어갈 수를 알 수 있습니다:

두개의 n 사이에는 정확히 n개의 수가 있습니다. 따라서, \(X\)와 \(Y\)의 사이는 \(Y - X - 1\)이므로, \(X\)와 \(Y\)에는 \(Y - X - 1\)이 들어있습니다.

문제의 예제 입력 1에서 얻을 수 있는 랭퍼든 수열은 다음과 같습니다.

[3, 1, 2, 1, 3, 2]

백트래킹

이전에 문제 N과 M에서도 풀어 봤듯이, 백트래킹은 DFS에서 조건에 맞지 않는 분기를 미리 쳐내 탐색 횟수를 줄이는 기법입니다. 따라서, DFS를 진행하기 전 어떤 조건이 탐색하기에 적합한지/적합하지 않은지 미리 판단할 조건이 필요합니다.

어떤 수열이 랭퍼든 수열이 되기 위한 조건을 살펴봅시다:

• 두 개의 n 사이에는 정확히 n개의 수가 있다.

다시 말해, 임의의 두 위치 \(i\)와 \(i + n + 1\)에는 \(n\)을 저장한다는 이야기입니다.

즉, 두 위치 \(i\)와 \(i + n + 1\)이 비어있는가?를 DFS 분기의 조건으로 생각할 수 있습니다. 여기서 \(n\)은 DFS 분기의 깊이로 설정하면 됩니다.

예외처리

앞서, \(X\)와 \(Y\)에는 \(Y - X - 1\)을 미리 넣어두었습니다. 따라서, DFS 분기의 조건이 성립하지 않습니다. 이 경우만 예외로 처리해 바로 다음 깊이로 DFS를 진행시키면 됩니다.

전체 코드

input = open(0).readline
N, X, Y = map(int, input().strip().split())

fixed = Y - X - 1

array = [0 for _ in range(2 * N + 1)]   # 1~2N번 인덱스까지 사용. (0번 미사용)
array[X] = array[Y] = fixed
cnt = 0

def dfs(depth):
    global cnt
    if depth == fixed:          # 이미 배치되어 있으므로 스킵.
        return dfs(depth + 1)
    if depth == N + 1:
        cnt += 1
        # print(array)    # DEBUG
        return

    # len(array) - (depth + 1) = 2*N+1 - depth - 1 = 2*N - depth
    for i in range(1, 2 * N - depth):
        if array[i] == 0 and array[i + depth + 1] == 0:
            array[i] = array[i + depth + 1] = depth
            dfs(depth + 1)
            array[i] = array[i + depth + 1] = 0

dfs(1)
print(cnt)