[백준] 15649번: N과M(1), 15650번 N과M(2) (파이썬)

https://www.acmicpc.net/problem/15649

문제를 보고, 이건 DFS로 풀어야겠는데? 라는 생각이 들었다. 문제 유형을 보니 '백트래킹'??

처음보는 문제 유형이었다.

무작정 문제를 풀 수는 없으니, 백트래킹이 무슨 유형인지 찾아봤다.

 

🐳 백트래킹이란?

백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하는 방법이다.
원하는 값이 아닐 경우 더 이상 탐색을 진행하지 않고 전 단계로 back해서 돌아가는 방법으로 이름 그대로 backtracking 알고리즘이다.

 

백트래킹은 DFS와 모두 탐색 알고리즘이어서 같은 유형의 문제는 두 방법으로도 모두 해결가능하다고 하다!

하지만 성능면에서는 백트래킹이 DFS보다 뛰어나다고 한다.

DFS는 트리의 바닥까지 모두 탐색해야하지만, 백트래킹은 불필요한 탐색을 피할 수 있기 때문이라고 한다.

 

코드로 이해하는게 가장 빠르니 N과 M(1)의 코드를 보자!

N,M = map(int,input().split())
answer = []

def back():
	# 원하는 길이의 순열이 완성되면 리턴
    if len(answer) == M:
        for i in answer:
            print(i, end=" ")
        print()
        return
    
    # i는 1부터 N까지의 숫자
    for i in range(1,N+1):
    	# 중복되지 않은 숫자만
        if i not in answer:
            answer.append(i)
            back()
		# return 되서 돌아오면 전 단계로 돌아감
            # 예를 들어 순열이 1,2,3이면 return 되서 돌아온 후 3이 pop되고
            # 1,2에서 다음 값을 찾는 형식으로 전 단계로 돌아가는 것
            answer.pop()
back()

 

똥손 ㅈㅅ

N이 4, M이 2일 때를 예시로 들면, 이 그림과 같다.

answer가 [1,2]가 되면 answer의 길이가 M과 같아지므로 재귀에서 빠져나와(answer가 [1,2]일 때) pop되어 다시 [1]로 돌아온다.

같은 방법으로 [1,3], [1,4]도 출력된다.

이후 [1,4]가 끝나면 [1]가 추가되었던 재귀에서 빠져나와 answer에서 1이 pop된다.

다시 for문이 돌아 answer가 [2]가 되고 이것을 for문이 끝날 때까지 반복한다.

 

DFS나 백트래킹 같이 재귀 개념이 들어가면 머리가 아파지는 것 같다😭

 

방금 문제의 업그레이드(?) 버전인 N과 M(2)를 바로 풀어보자!

https://www.acmicpc.net/problem/15650

 

이번엔 1 부터 N까지의 순열을 구하는데, 중복이 없게 구해야한다.

아까 코드를 조금 고치면 되겠구나 생각했다.

N,M = map(int,input().split())
answer = []

def back():
    if len(answer) == M:
        for i in answer:
            print(i, end=" ")
        print()
        return
    
    for i in range(1,N+1):
        if i not in answer:
            if answer == []:
                answer.append(i)
                back()
                answer.pop()
            elif i > answer[-1]:
                answer.append(i)
                back()
                answer.pop()
            
back()

i가 answer의 마지막 값보다 큰 경우면 answer에 추가하면 된다!

answer가 빈 경우는 answer[-1]가 존재하지 않으므로 따로 빼주었다.

백트래킹 너 재밌다☝️