백준 2529 : 부등호 (Python)

본문 링크

def Backtracking( visit , start , K):

    global String,MAX_STR,MIN_STR



    if len(K)==N+1:
        if K<MIN_STR:
            MIN_STR=K
        elif K>MAX_STR:
            MAX_STR=K
        return
    if K<MAX_STR and K>MIN_STR:
        return

    for i in range(start,N):
        check=False
        for j in range(10):
            if L[i]==">" and not visit[j]:
                if int(K[-1])>j:
                    visit[j] = True
                    check = True
                    Backtracking(visit , start+1 , K+str(j) )
                    visit[j]= False
                    check = False
            elif L[i]=="<" and not visit[j]:
                if int(K[-1])<j:
                    visit[j] = True
                    check = True
                    Backtracking(visit , start+1  , K+str(j))
                    visit[j]=False
                    check = False # 백트래킹후 False 처리도 해줘야함.

        if not check:
            return
N=int(input())
L=list(input().split())


MIN_STR="99999999999" ; MAX_STR="0"

for i in range(10):
    visit = [False] * (10)
    visit[i]=True
    Backtracking(visit , 0 , str(i) )

print(MAX_STR)
print(MIN_STR)

📌 어떻게 접근할 것인가?

백트래킹을 사용해 풀었습니다.

MIN_STR="99999999999" ; MAX_STR="0"

재귀로 특정 문자열을 만들었을때 최대 최소를 저장할 문자열을 선언해줍니다.

for i in range(10):
    visit = [False] * (10)
    visit[i]=True
    Backtracking(visit , 0 , str(i) )

0부터 9 까지 처음수를 잡아주고 재귀를 실행합니다.

for i in range(start,N):
	check=False
	for j in range(10):
    	if L[i]==">" and not visit[j]:
			if int(K[-1])>j:
				visit[j] = True
				check = True
				Backtracking(visit , start+1 , K+str(j) )
				visit[j]= False
				check = False
		elif L[i]=="<" and not visit[j]:
			if int(K[-1])<j:
				visit[j] = True
				check = True
				Backtracking(visit , start+1  , K+str(j))
				visit[j]=False
				check = False # 백트래킹후 False 처리도 해줘야함.

	if not check:
		return

백트래킹의 핵심이 되는 부분입니다. 첫번째 반복문의start 를 통해서 이전에 썼던 부등호는 안쓰도록 처리해줍니다.

부등호가 > 일때의 조건만 보겠습니다.

if L[i]==">" and not visit[j]:
	if int(K[-1])>j:
		visit[j] = True
		check = True
		Backtracking(visit , start+1 , K+str(j) )
		visit[j]= False
		check = False

만약 부등호가 > 이고 방문하지 않은 지점이라면
그리고 문자열의 마지막 값과 j 값의 대소관계가 올바르다면 , visit 방문배열을 True 로 바꿔주고 check 변수도 True 로 바꿔준다음에 재귀를 실행합니다.
이때 start 는 1 을 추가함으로써 다음 부등호를 탐색할수 있도록 하고 K+str(j) 를 통해 문자열의 길이를 하나 증가시킵니다.
이후 백트래킹을 위해 visit[j]=False , check=False 처럼 되돌려 줍니다.

부동호가 반대일때는 대소관계만 바꿔주고 그대로 해주시면됩니다.

if not check:
	return

처음에 check=False 를 선언하였는데 , 만약 0 부터 9 까지 아무숫자를 넣을수 없으면 return 을 해줘야 합니다.

if len(K)==N+1:
	if K<MIN_STR:
		MIN_STR=K
	elif K>MAX_STR:
    	MAX_STR=K
    return
if K<MAX_STR and K>MIN_STR:
	return

개인적으로 이부분이 가장 중요하다고 생각합니다.
특히 2번째 조건이 가장 중요합니다.

첫번째 조건문을 통해서 문자열의 길이가 $N+1$ 에 도달하면 최대값과 최소값을 갱신해줍니다.

그리고 재귀를 탐색하던 도중에 if K<MAX_STR and K>MIN_STR: 라면 즉시 종료해줍니다.

즉 최소값을 찾는데 현재 저장한 값이 012 라면 굳이 12 이후로 탐색할 필요가없습니다.
반대로 최대값을 찾는데 현재 저장한 값이 897 이라면 굳이 78 이후로 탐색할 필요가없습니다.

따라서 의미없는 부분을 즉각 종료해줘야지 제한시간안에 문제를 풀 수 있습니다.

백트래킹은 구현도 되게 중요하지만 문제에서 주어지는 $N$ 의 범위가 작다고 해서 구현만 해주시면 안됩니다.

꼭 필요없는 부분에 대해서는 탐색하지 않도록 최적화를 해주는것 또한 매우 중요합니다.