[BOJ] 2529. 부등호(Python) / DFS

www.acmicpc.net/problem/2529

2529번: 부등호

 

제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾는 문제

• 사용 알고리즘 : DFS 재귀로 순열 구현하기
• 간단한 DFS 문제로 순열을 구하고 들어오는 각 숫자가 부등호에 부합하는 경우에만 재귀로 수를 더하며 넘기고,
• 부등호에 맞지 않다면 그냥 넘어간다.(isSatisfy 함수에서 확인)
• 가능한 경우일 때마다 최솟값, 최댓값을 갱신한다.
• 출력 시, 최댓값은 그대로 출력, 최솟값은 맨 앞 자리 수가 0이라면 길이가 N+1보다 작을 것이므로 문자열로 "0"을 더해 출력한다. 그렇지 않다면 그대로 출력한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# 부등호 만족하는지 True, False로 리턴
def isSatisfied(num1, sign, num2):
    if sign == ">":
        return num1 > num2
    else:
        return num1 < num2

# 재귀로 순열 구현
def perm(depth, temp):
    global MIN, MAX
    if depth == N+1:
        # print(temp)
        MIN = min(MIN, int(temp))
        MAX = max(MAX, int(temp))
        return
    for n in range(10):
        if check[n]:
            continue
        # 첫 번째 수이거나 부등호를 만족하는 경우에만 방문 표시하고 재귀로 넘어감
        if depth == 0 or isSatisfied(int(temp[-1]), sign[depth-1], n):
            check[n] = 1
            perm(depth+1, temp + str(n))
            check[n] = 0

# main
N = int(input())
sign = input().split()

MIN, MAX = float('inf'), float('-inf')
check = [0] * 10
perm(0, "")
print(str(MAX))
if len(str(MIN)) < N+1:
    print("0"+str(MIN))
else:
    print(str(MIN))

---

• 시간 : 176ms / 메모리 : 124044kb
• 고찰 : 아무래도 완전탐색이다보니 시간이 좀 걸리는 편인 것 같다. 실버 문제이기도 하고 dfs 재귀로 순열을 구해 간단히 풀 수 있던 문제이다. DFS 문제 좀더 풀어봐야겠다.