[백준/15649/파이썬]N과M(1) - 백트래킹

---

소스코드 (permutations)

from itertools import permutations

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

n_list = [i+1 for i in range(n)]

ans = list(permutations(n_list, m))

for i in ans:

  print(' '.join(map(str, i)))

 

알고리즘

파이썬에 있는 permutations를 이용하면서 풀면 끝 ~ 이라는 생각으로 풀었다.근데 다른 사람들은 어떻게 풀었는지 검색을 해보니 백트래킹 기법을 이용하여 풀었다고 해서 뭐시여,,,하고 다시 풀어봤다.

 

---

소스코드 (backtracking)

def dfs():

    if len(s) == m:

        print(' '.join(map(str, s)))

        return

    for i in range(1, n+1):

        if visited[i]:

            continue

        visited[i] = True

        s.append(i)

        dfs()

        s.pop()

        print(s)

        print(visited)

        visited[i] = False

            

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

s = []

visited = [False] * (n+1)

dfs()

알고리즘

백트래킹이 뭔지 공부를 해보는 계기가 되었는데

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

라고 정의가 나와있다. 일반적인 dfs와 비슷한데 백트래킹은 안될것 같으면 가지쳐버리는 것이다.

뭔가 인공지능 배울때 a-b prunning 이었나 그게 떠올랐다. 

아무튼 백트래킹을 이용하면 시간을 줄여줄 수 있다고 한다.

코드는 재귀 dfs 바탕으로 진행된다.