1248: 맞춰봐

• 구하고자 하는 sequence of integers에서 integer set이 {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}으로, 총 21개임 -> 모든 경우를 확인한다면 시간 복잡도가 21의 n승임 -> backtracking 필요
• 1) 매 depth마다 visit list에 append하는 node의 부호는 Sign Matrix의 대각선에 위치한 부호와 일치해야함
  -> 일치한다면 visit list에 해당 node를 append
• 2) 나머지 경우는 for x in range(depth-1, -1, -1)을 순회하며 역순으로 sum을 구해가면서 부호를 확인하는 과정이 필요함
  -> 만약 모든 부호를 만족한다면 (err == 0), 다음 depth로 진행 ( dfs(depth + 1) )
  -> 만약 한번이라도 만족하지 않는 경우가 있다면 err = 1; break 해주고 visit.pop()을 하여 해당 노드를 다시 제거해줌
• 조건을 만족하는 sequence of integers를 한 번만 출력하면 되기 때문에, 한 번 출력한 경우 exit(0)을 하여 process를 종료시킴

import sys
from collections import deque

n = int(input())
S = deque(list(sys.stdin.readline()[:-1]))
Matrix = []
for i in range(n):
    tmp = []
    for j in range(n):
        tmp.append(-1)
    Matrix.append(tmp)
for i in range(n):
    for j in range(i, n):
        Matrix[i][j] = S.popleft()
visit = []

def satisfy(sign, num):
    if sign == '-' and num < 0:
        return True
    elif sign == '+' and num > 0:
        return True
    elif sign == '0' and num == 0:
        return True
    else:
        return False

def dfs(depth):
    if depth == n:
        print(" ".join(map(str, visit)))
        exit(0) #process 종료
    for i in range(-10, 11):
        if satisfy(Matrix[depth][depth], i):
                visit.append(i)

                s = visit[-1]; err = 0
                for x in range(depth-1, -1, -1):
                    s += visit[x]
                    if not satisfy(Matrix[x][depth], s):
                        err = 1; break

                if err == 0:
                    dfs(depth+1)

                visit.pop()
            
dfs(0)