[백준] 15649번(python 파이썬)

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

 

---

백트래킹의 기초 문제이다.

완전탐색을 하게된다. 재귀를 이용하여 풀게되는데 이때 더이상 탐색을 할 필요가 없다면 재귀 탐색을 멈추게된다.

 

첫 풀이

해당 숫자에 visited를 부여하여 방문을 했는지 계속 체크하고 visited를 deepcopy하여 넘겨주는 식으로 하였다.

이렇게 하면 숫자가 많아질수록 list를 엄청나게 많이 만들게 되고 또한 deepcopy를 하는데에 시간도 길리기 때문에 메모리, 시간 둘다 비효율적이다. .......

 

정답 풀이

visited라는 상태 체크를 하는 것이 아니라, 방문한 숫자를 집어넣는 list를 만들어 풀게 된다.

1. 깊이가 출력하는 숫자의 길이가 같을경우 재귀를 멈춘다.

2. i : 1 ~ n 까지 반복을 하여 list에 i에 해당하는 숫자가 없을경우 i를 append한후 list를 다시 재귀를 돌린다.

 

input = n : 4, m : 2

                                                   

---

혼자서 푼 풀이..

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

visited = [False] * (n + 1)
def Dfs(visited, depth, temp_str):
    if depth == m:
        print(temp_str.strip())
        return
    for i in range(1, n + 1):
        if not visited[i]:
            temp_visited = copy.deepcopy(visited)
            temp_visited[i] = True
            prev = temp_str + " " + str(i)
            Dfs(temp_visited, depth + 1, prev)


visited[0] = True
Dfs(visited, 0, "")

배열을 계속 copy를 하기때문에 시간, 메모리 에서 엄청나게 비효율적..

 

 

정답 풀이

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

def BackT(depth):
    if depth == m:
        for i in solve:
            print(i, end=' ')
        print()
        return
    for i in range(1, n + 1):
        if i not in solve:
            solve.append(i)
            BackT(depth + 1)
            solve.pop()

BackT(0)