[ 백준 7490 ] 0 만들기 - Python

문제 보기

이 문제는 DFS 문제이다.

 

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성해야 한다.

 

모든이라는 글자가 나오면 자연스럽게 완전 탐색(Brute Force)을 생각하게 된다. 또한 자연수 N의 범위가 크지 않아서 완전 탐색으로도 충분히 구현 가능할 것이라고 생각하였다.

 

시간제한이 충분하지 않을 때는 BFS를 많이 사용하지만 여유로우면 DFS를 즐겨 사용한다. 해당 문제는 위에서 말했듯이 시간제한이 여유로웠으며 순차적으로 연산('+', '-', '')을 삽입하는 DFS가 가장 구현하기 편해 보였다. 

 

알고리즘 구현 과정은 아래와 같다.

1. 1 ~ N의 값을 갖는 리스트를 생성한다.

2. 숫자 사이에 연산을 대입한다. ('+', '-', '' 모든 경우를 고려한다)

3. 연산 대입을 완료한 후 eval 함수를 사용하여 문자열 연산 값이 0인지 확인한다.

4. 결괏값이 0이면 출력한다.

5. 위 과정을 테스트 케이스만큼 반복한다.

 

코드

def dfs(idx, arr):  # 인덱스, 문자열 수식
    if idx == N - 1:
        eval_list = "".join(map(str, arr))
        result = eval(eval_list)
        if result == 0:
            for i in range(len(arr)):
                if arr[i] == "":
                    print(" ", end="")
                elif i == len(arr) - 1:
                    print(arr[i])
                else:
                    print(arr[i], end="")
    else:
        arr.insert(idx * 2 + 1, '')  # 숫자 이어 붙이기
        dfs(idx + 1, arr)
        arr.pop(idx * 2 + 1)

        arr.insert(idx * 2 + 1, '+')  # +
        dfs(idx + 1, arr)
        arr.pop(idx * 2 + 1)

        arr.insert(idx * 2 + 1, '-')  # -
        dfs(idx + 1, arr)
        arr.pop(idx * 2 + 1)


if __name__ == "__main__":

    testcase = int(input())  # 테스트 케이스의 개수
    for _ in range(testcase):
        N = int(input())  # 1 ~ N
        N_list = [i for i in range(1, N + 1)]
        dfs(0, N_list)
        print("")