[백준 #10974 파이썬] 모든 순열

완전 탐색 알고리즘 

---

 

의미 그대로 전체를 탐색할 수 있도록 고안하는 알고리즘입니다.

문제를 해결함에 있어 어떻게 탐색을 해야할 지 다양하게 고민해보는 것이 중요합니다.

단순히 순차열적으로 해결할 수도 있고, 탐색에 어떤 조건이나 기준을 세워 전체를 바라보는 방법도 있습니다.

여러 방법으로 해결할 수는 있겠지만, 메모리 사용을 줄이고 탐색의 시간을 감소시키기 위해 더 효율적인 방법에 대해

고민하는 방법이 알고리즘 해결에 있어 가장 중요한 부분입니다.

 

 

10974 모든 순열

 

1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

10974번: 모든 순열

 

 

N!줄에 걸쳐서 모든 순열을 출력해야 하는 문제입니다.

이 문제를 생각함에 있어 가장 중요하게 생각한 건 재귀는 반드시 사용될 것이라는 겁니다.

 

for문 내에 단순한 코드만으로는 문제를 푸는 데에 한계가 있습니다. 직선방향(증가,감소)등으로 탐색을 진행하기 때문에 실행 예시처럼 다시 처음으로 돌아가는 경우를 고려하기는 힘듭니다.

그렇기에 for문 내에서 새로운 작업의 필요성을 항상 생각해야 합니다. 그렇게 생각한 방법이 바로 재귀의 활용입니다.

 

우선 함수를 하나 만들어줍니다.

def find_permutation():

 

그리고 이 안에 탈출 조건을 먼저 생각해 주어야 합니다.

결과를 보면 하나의 경우의 수마다 1~n까지의 수들이 순서에 따라 출력이 됩니다. 

그점에 착안하여 빈 리스트를 만들어주고 리스트의 길이가 n과 같으면, 리스트만 벗겨 하나의 경우의 수를 출력하고 함수를 탈출할 수 있도록 하였습니다.

 

def find_permutation():
    if len(l) == n:
        print(*l,sep = ' ')
        return

이제는 가장 중요한 탐색 과정입니다.

지금까지 공부를 함에 있어  탐색에 가장 중요한 점은 방문 여부를 확인하는 것입니다.

dfs bfs나 다른 탐색에 있어서도 해당 노드를 방문했는지 여부를 확인하는 것은 효율적인 코드를 작성하기 위해선 가장 중요한 요소라고 생각합니다. 이 부분을 이번 문제 해결에 있어서도 적극적으로 활용하려고 합니다.

 

우선 1~n까지의 값이 있는지 확인할 수 있도록 for문의 범위를 설정해줍니다.

이후 값이 리스트 l에 존재하는 지 확인하는 과정이 필요합니다.

없다면 값을 추가해주도록 하는 과정까지 구현했습니다.

n = int(input())
l = []

def find_permutation():
    if len(l) == n:
        print(*l,sep = ' ')
        return
    
    for i in range(1,n+1):
        if i not in l:
           l.append(i)

그런데 값을 추가해 주기만 하면 출력 결과와 같은 결과는 얻기 어렵습니다.

여기 부근부터는 재귀의 필요성을 인지할 수 있었습니다. 이때 재귀를 한번 사용해보겠습니다.

그러면 진행은 다음과 같습니다.

 

ex ) n=3의 경우

 

 

첫 def       for문의 i값 : 1  (리스트 l : [1])

       두번째 def      for문의 i값 : 1 ( 1이 l에서 존재하므로 첫번째 i 패스)

                                                : 2 ( 2는 l에 존재하지 않으므로 추가한다. 그리고 다시 함수 중첩 리스트 l : [1,2])

            세번째 def     for문의 i값 : 1,2 (1,2는 l에서 존재하므로 첫번째, 두번째 i는 패스)

                                                    : 3(3은 l에 존재하지 않으므로 추가한다. 그리고 다시 함수 중첩 리스트 l : [1,2,3])

                            네번째 def       리스트 l의 길이가 3이므로 이 리스트를 출력한다. ( 1 2 3 출력)

 

하지만 다음과 같은 과정을 거친 후에는 처리를 어떻게 해야 할 지 판단이 어렵습니다.

일단 순서대로 이후의 결과를 살펴보면 네번째 def가 종료되었고 그러면 세번째 def의 for문으로 돌아와야 합니다. 

세번째 def 의 상황은 for문의 i가 (1,2,3)모두 반복되었음을 확인할 수 있습니다.

그리고 두번째 def의 상황은 for문의 i가 (1,2)까지만 반복되어 있습니다.

두번째 def는 for문이 종료되어 있지 않죠. 이 점을 활용하고자 합니다.

 

한번 리스트의 마지막 값을 빼버리는 시나리오를 추가해보겠습니다.

n = int(input())
l = []

def find_permutation():
    if len(l) == n:
        print(*l,sep = ' ')
        return
    
    for i in range(1,n+1):
        if i not in l:
            l.append(i)
            find_permutation()
            l.pop()

find_permutation()

                                                     

이렇게 되면 세번째 def는 마지막 값 3을 빼버리게 되겠죠

그러면 두번째 def로 돌아오게 됩니다. 그런데 우리는 for문의 i = 2가 이전 코드에서는종료되었지만

l.pop()이 아직 반영이 되지 않았음을 확인할 수 있습니다. 현재 리스트 l은 [1,2]죠

이 상태에서 l.pop을 실행하면 l은 [1]이 되고 for문의 i=3이 실행될 차례임을 확인할 수 있습니다.

 

그러면 바로 for문 내의 if문에 따라 l은 [1,3]이 되며 다시 세번째 def로 진입하게 됩니다.

여기에서는 i = 1에서 pass, 2에서 추가, 3에서 pass가 되며 네번째 def에서  1 3 2 가 출력됩니다. 신기하죠!

그러면 4번째 def 종료 세번째 def 종료 두번째 def 종료, 그리고 첫번째 for문의 i가 1이 수행되었음을 알 수 있습니다.

 

그러면 첫번째 for문의 i가 2인 경우로 다시 시작되겠죠! 이렇게 해서 6가지 경우의 수를 얻게되면 첫번째 for문도 종료가 될 것입니다.

 

이러한 방식의 풀이는 조금 생소하게 느껴지실 수 있습니다. 저도 이 문제를 완전탐색에 대해 먼저 공부하지 않고 풀어보았을 때는 굉장히 어려운 풀이었습니다. 이 문제를 통해서 완전 탐색에 대해 조금더 이해를 하고 더 경험이 쌓여나간다면 dfs,bfs, 그래프 탐색과 같은 과정에 대해서도 충분히 응용과 활용이 가능할 것입니다! (물론 저도 더 경험을 쌓아야합니다...!)