[백준 알고리즘/Python3] 15649 N과 M(1)

문제이해

처음 문제를 이해하는대 어려웠습니다.

DFS의 계념만 이해하고 있었지 실제로 구현해보지 않아서 다른 사람의 DFS 코드를 보고 공부한 후 문제를 풀었습니다

 

백트레킹을 DFS를 이용해 풉니다.

1부터 중복된 숫자 없이 m번 수열을 만들면 됩니다.

 

n, m = map(int, input().split())

base = [] # 재귀함수를 이용하여 m개의 수열을 저장하기 위한 리스트

def dfs():
    #리스트에 들어간 수열들이 m개가 되면
    #리스트에 들어있는 숫자들을 모두 출력하고 함수를 나온다.
    if(len(base) == m):                
        print(' '.join(map(str,base)))
        return

    for i in range(1, n+1):
        if i not in base:  # 리스트 s 중복여부 확인
            base.append(i) # 중복이 아니면 숫자 i를 리스트 s에 넣기
            dfs() #
            base.pop()

dfs()

 

4 2를 입력하면

[1] -> [1,2] ->[1] -> [1,3] -> [1] -> [2] -> [2,1] -> [2] -> [2,3] -> [2] -> [2,4] ...

        출력    pop    출력    pop  (재귀)    출력    pop    출력    pop    출력 ....

 

 

 

DFS를 이용해 재귀를 하면 fork하는 것과 비슷할 거같습니다.

또다른 함수가 스택에 쌓이고 다른 프로세스가 함수의 처음부터 다시 시작하는 것을 파악했습니다.

 

파이썬에서 리스트를 출력할 때 for문을 자주 썻습니다.

join()과 map()으로 편리하게 사용할 수 있게 됐습니다.

 

• join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수입니다.
• map은 리스트의 요소를 지정된 함수로 처리해주는 함수입니다.
• map(함수, 리스트)

 

 

참고

https://jiwon-coding.tistory.com/21