연습 문제

백트래킹 문제는 겉모습이 달라도 "무엇을 한 단계로 볼 것인가, 어떤 조건에서 자를 것인가" 두 가지만 정하면 대부분 같은 틀로 풀립니다. 아래 네 문제를 직접 풀어 본 뒤 접근 방법과 풀이를 비교해 보세요.

문제 1: 괄호 짝 만들기

정수 n이 주어질 때, 여는 괄호와 닫는 괄호를 n개씩 써서 만들 수 있는 올바른 괄호 문자열을 모두 구하세요. 예를 들어 n = 2이면 (())와 ()()입니다.

접근: 한 글자씩 붙입니다. 여는 괄호는 n개보다 적게 썼을 때만, 닫는 괄호는 지금까지 연 괄호보다 적게 닫았을 때만 붙일 수 있습니다. 이 두 조건이 잘못된 문자열을 처음부터 막는 가지치기입니다.

def parentheses(n):
    out = []

    def dfs(s, opened, closed):
        if len(s) == 2 * n:
            out.append(s)
            return
        if opened < n:
            dfs(s + "(", opened + 1, closed)
        if closed < opened:
            dfs(s + ")", opened, closed + 1)

    dfs("", 0, 0)
    return out

print(parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

문제 2: 격자에서 단어 찾기

글자가 적힌 2차원 격자와 단어 하나가 주어집니다. 상하좌우로 이웃한 칸을 따라가며 단어를 만들 수 있는지 판단하세요. 한 칸은 한 번만 쓸 수 있습니다.

접근: 첫 글자가 맞는 칸마다 탐색을 시작합니다. 현재 칸을 #으로 바꿔 사용 중임을 표시하고(선택), 네 방향으로 다음 글자를 찾은 뒤(탐색), 원래 글자로 되돌립니다(되돌리기). 글자가 다르면 즉시 돌아갑니다.

def exists(grid, word):
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != word[i]:
            return False
        saved, grid[r][c] = grid[r][c], "#"
        found = any(dfs(r + dr, c + dc, i + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        grid[r][c] = saved
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

board = [list("CAT"), list("OXD"), list("DEN")]
print(exists(board, "CODE"), exists(board, "COAT"))  # True False

문제 3: 중복 원소가 있는 순열

[1, 1, 2]처럼 같은 값이 섞인 목록의 서로 다른 순열만 구하세요. 결과에 같은 순열이 두 번 나오면 안 됩니다.

접근: 먼저 정렬합니다. 같은 깊이에서 같은 값을 두 번 고르면 같은 가지가 반복되므로, 바로 앞의 같은 값이 아직 쓰이지 않았다면 지금 값은 건너뜁니다. 결과를 집합에 넣어 중복을 지우는 것보다 탐색 자체가 줄어듭니다.

def unique_permutations(nums):
    nums = sorted(nums)
    used = [False] * len(nums)
    result, path = [], []

    def dfs():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

print(unique_permutations([1, 1, 2]))  # [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

문제 4: 스도쿠 풀기

빈 칸이 0으로 표시된 9×9 스도쿠 판을 채우세요. 해가 하나 있다고 가정합니다.

접근: 행, 열, 상자마다 이미 쓴 숫자를 집합으로 들고 있으면 제약 검사가 O(1)입니다. 빈 칸 목록을 차례로 채우다가 넣을 숫자가 없으면 False를 돌려 앞 칸에서 다음 숫자를 시도하게 합니다. 해를 찾으면 True를 위로 전달해 더 이상 되돌리지 않습니다.

def solve_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d:
                rows[r].add(d); cols[c].add(d); boxes[r // 3 * 3 + c // 3].add(d)
            else:
                empty.append((r, c))

    def fill(k):
        if k == len(empty):
            return True
        r, c = empty[k]
        b = r // 3 * 3 + c // 3
        for d in range(1, 10):
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            board[r][c] = d
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            if fill(k + 1):
                return True
            rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
        board[r][c] = 0
        return False

    return fill(0)

더 빠르게 하려면 매번 남은 빈 칸 가운데 후보가 가장 적은 칸을 골라 채우세요(MRV). 어려운 퍼즐에서 탐색 노드가 크게 줄어듭니다.

정리

• 한 단계의 단위(글자, 칸, 원소)와 가지치기 조건을 먼저 정하면 코드는 같은 틀로 쓰입니다.
• 중복 해는 결과를 걸러 내기보다 같은 깊이에서 같은 선택을 막아 처음부터 만들지 않는 편이 좋습니다.
• 해 하나만 필요하면 True를 돌려 탐색을 일찍 끝냅니다.