백준 1248번 - 맞춰봐(Python)

초급 스터디 - 02 Backtracking 예제

* 강의를 들으며 배운 것을 정리하는 포스팅입니다. 제가 생각해낸 아이디어가 아닙니다. *

문제

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

1248번: 맞춰봐

풀이

입력으로 주어진 조건을 n x n 배열에 저장한 다음 각 조건을 검사하는 방법은 1)행 단위, 2)열 단위의 두 가지 방법이 있다.

1)
행 단위로 검사를 하는 경우는 n = 4일 때 0부터 0까지의 합, 0부터 1까지의 합, 0부터 3까지의 합... 2부터 2까지의 합, 2부터 3까지의 합... 3부터 3까지의 합 순서로 보는 것이다. 이 경우는 백트래킹을 할 때 어느 레벨까지 백트래킹을 해야 할 지 감이 잘 안 잡힌다.

2)
열 단위로 검사를 하는 경우는 다시 위에서 아래로 검사하는 경우(0부터 n-1까지)와 아래에서 위로 검사하는 경우(n-1부터 0까지)의 2가지 경우로 나뉜다. 강사님께서는 아래에서 위로 검사하는 경우를 선택하셨는데, 그 이유는 아래에서 위로 검사를 하게 되면 각 열마다 처음 실시하는 검사는 무조건 x에서 x까지의 합이므로 x번째 수의 부호를 바로 알 수 있기 때문이다. 열 단위 검사를 했을 때의 장점은 수열의 i번째 수를 확실하게 정할 수 있으므로 이전 단계의 숫자를 다시 고르기 위해 돌아갈 필요가 없다는 것이다.

check(index)
현재 index 번째 수를 채울 때 sign[i][index]의 부호조건을 만족하는지 아닌지 검사하는 함수다. index부터 1씩 감소하며 0까지의 조건을 만족하는지 확인한다. 즉 i부터 i번째까지의 합, i-1부터 i번째까지의 합, ... 0부터 i번째까지의 합 순서로 확인한다. 위에서 우리가 열 단위/아래에서 위로 검사하는 방법을 채택했기 때문이다.
조건을 하나라도 만족하지 않으면 False, 전부 다 만족하는 경우 True를 리턴한다.

solve(index)

• Base case
  index == n인 경우. check(index)를 만족해야 solve(index + 1)을 호출할 수 있으므로 Index == n이면 모든 부호 조건을 만족한 것이다.
• Recursive case
  1. 현재 index가 n 미만이고, sign[index][index]의 부호 조건이 0인 경우 => index ~ index번째 수의 합이 0이 되려면 index번째 수는 무조건 0이 되어야 하므로 예외처리
  2. 그 외의 경우 => i의 값이 1부터 10까지 증가하는 반복문 안에서 i에다가 부호를 붙여준 후(sign[index][index] 참고) check()로 테스트, 만족하는 경우 solve(i + 1) 재귀 호출하여 다음 단계 진행

코드

# 백트래킹
# 가능한 모든 경우의 수의 최대값이 16조 이상이므로 완전 탐색으로는 제한 시간(2초)안에 구현 불가
# 필요한 정보, Base Case, Recursive Case 생각하기


def check(index):  # 현재 index 번째 수를 채울 때 sign[i][index]의 부호조건을 만족하는지 아닌지 검사하는 함수(역순)
    s = 0
    for i in range(index, -1, -1):
        s += ans[i]
        if sign[i][index] == 0:
            if s != 0:
                return False
        elif sign[i][index] < 0:
            if s >= 0:
                return False
        elif sign[i][index] > 0:
            if s <= 0:
                return False
    return True


def solve(index):   # 현재 index 번째 수를 채우는 함수
    if index == n:  # check(index)를 만족해야 solve(index + 1)의 재귀호출이 가능하므로 index = n이면 sign 배열의 모든 부호 조건을 만족한 경우이므로 True 리턴
        return True
    if sign[index][index] == 0:  # recursive case 1: 현재 index 수가 n 미만이고 0이면 바로 조건 검사 후 재귀 호출
        ans[index] = 0           # index ~ index 번째의 수의 합이 0이 되려면 ans[index]가 0이 되어야 함!
        return check(index) and solve(index + 1)

    for i in range(1, 11):       # recursive case 2: 현재 index 수가 n 미만이고 0이 아니면 index 번째 부호를 붙인 후 조건 검사 후 재귀 호출
        ans[index] = i * sign[index][index]
        if check(index) and solve(index + 1):
            return True
    return False


n = int(input())
ans = [0] * n  # 정답이 저장될 리스트
signs = list(input())  # 부호 조건이 저장될 리스트
sign = [[0 for _ in range(n)] for _ in range(n)]

idx = 0
# +, - 대신 1, -1을 저장해 solve()에서 해당 인덱스의 수에 부호를 쉽게 붙일 수 있도록 함
for i in range(0, n):
    for j in range(i, n):
        if signs[idx] == '+':
            sign[i][j] = 1
        elif signs[idx] == '-':
            sign[i][j] = -1
        idx += 1

solve(0)
print(' '.join(map(str, ans)))