2019.03.02) 백준 dfs 특집 2편 - 14888, 2800(PyPy3)

dfs를 이런느낌으로 응용할수 있구나를 알았다.

괄호 제거는 좀 설명이 부족해서 질문되있는거 보고 테스트케이스 해보고 해결했다.

중복이 안되고, 제데로 된 수식이 아니면 진행하지 않는다는걸 좀 문제에 써주지;;

14888번

# 깊이 위주 탐색
def dfs(now, index, ns):
    n1, n2, n3, n4 = ns
    # 만약 입력값 넘어가면 탐색 종료
    if index == c:
        r.append(now)
        return
    # +
    if n1 > 0:
        dfs(now + l[index], index + 1, (n1 - 1, n2, n3, n4))
    # -
    if n2 > 0:
        dfs(now - l[index], index + 1, (n1, n2 - 1, n3, n4))
    # *
    if n3 > 0:
        dfs(now * l[index], index + 1, (n1, n2, n3 - 1, n4))
    # //
    if n4 > 0:
        # C++식 나누기를 구현
        if now < 0:
            dfs(-1 * ((-1 * now) // l[index]), index + 1, (n1, n2, n3, n4 - 1))
        else:
            dfs(now // l[index], index + 1, (n1, n2, n3, n4 - 1))
 
 
r = list()
c = int(input())
l = list(map(int, input().split(' ')))
 
dfs(l[0], 1, map(int, input().split(' ')))
print(max(r))
print(min(r))
 

2800번

s = input()
 
c = list()
 
 
# 스택과 dfs를 동시에 사용
def dfs(now, index, stack):
    # 입력수열 이상으로 탐색하면 종료
    if len(s) == index:
        # 입력수열이랑 똑같으면 그냥 넘김, 완벽한수열이 아닐떄도 넘김
        if s == now or len(stack) != 0:
            return
        # 만약 중복이 아니면 추가
        if not now in c:
            c.append(now)
            return
    # 탐색한 문자가 ( 이면
    elif s[index] == '(':
        # ( 추가하고 스택에 1 추가해서 넘기고
        dfs(now + s[index], index + 1, stack + [1])
        # ( 추가 안하고 스택에 0 추가해서 넘김
        dfs(now, index + 1, stack + [0])
    # 탐색한 문자가 ) 이면
    elif s[index] == ')':
        # 스택 길이가 없을땐 불가능수열로 판단
        if len(stack) == 0:
            return
        # 바로 전 스택이 0이면
        if stack[-1] == 0:
            # 이번 탐색을 추가를 안함
            dfs(now, index + 1, stack[:-1])
        # 바로 전 스택이 1이면
        if stack[-1] == 1:
            # 이번 탐색을 추가함
            dfs(now + s[index], index + 1, stack[:-1])
    else:
        # 다른 문자열이면 평범하게 넘김
        dfs(now + s[index], index + 1, stack)
 
 
dfs('', 0, [])
c.sort()
print('\n'.join(c))