[백준] 15651 N과 M (3) (실버3) / 백트래킹

문제요약

나의 코드 및 설명 - 리스트를 넘겨주는 풀이

• 함수를 호출할 때마다 리스트를 넘겨준다.

def dfs(index, temp_list):
    if index == m:
        ans.append(temp_list)
        return
    for i in range(1, n+1):
        dfs(index+1, temp_list+[i])

n, m = map(int, input().split())
ans = []

dfs(0, [])
for j in ans:
    print(*j)

 

나의 코드 및 설명 - 리스트를 넘겨주지 않는 풀이

• 함수를 호출할 때마다 리스트를 넘겨주지 않고, ans에 직접 수열을 추가하여 출력한다. 단, 이렇게 풀이하게 될때는 리턴될 때 ans에 이전에 추가된 수열을 pop 메서드를 통해 꺼내주어야 한다.

def dfs(index):
    if index == m:
        print(" ".join(map(str, ans)))
        return
    for i in range(1, n+1):
        ans.append(i)
        dfs(index+1)
        ans.pop()
n, m = map(int, input().split())
ans = []
dfs(0)

피드백

문제를 트리를 그려서 표현하기 위해 노력하고 있고, 백트래킹의 기본구조를 최대한 지키면서 문제를 풀기 위해 노력중이다. 확실히 이 두가지를 지키면서 문제를 푸니 기본기도 잡히고 안정되어져 가는 것 같다.