[백준 15651] 백트래킹 (완전탐색)

나의 첫 백트래킹 문제.. 내 힘으로 못 풀었다.

검색을 통해 공부하면서 이해하고 두가지 방법을 알게 됐다.

 

> 1번째 방법

a,b = map(int, input().split())
l = [0 for _ in range(b)]

def back(a,b,i=0):
    if b==i:
        print(*l)
        return
    for j in range(a):
        l[i] = j+1
        back(a,b,i+1)

back(a,b)

 

이게 처음 푼 코드

재귀를 이용해 해결하는 방법이다.

6번째줄 print(*l)은 처음 알게 된 건데, 반복문을 쓰지 않고 리스트 내 모든 원소를 공백으로 구분해서 출력할 수 있다.

다른 사람들 답을 보면서도 항상 나왔던 건데, 찾아보지 않다가 이제야 알게 됐다.

a = [1,2,3,4]

for i in a:  #1
    print(i, end=' ')
    
print(*a)    #2

 

위의 코드가 한 줄로 줄어드는 것이다. 깔끔한 코드를 좋아하는 나로선 이제라도 알아서 다행이다.

---

> 2번째 방법

from itertools import product
a,b = map(int,input().split())
for j in [i for i in product(range(1,a+1),repeat=b)]:
    print(*j)

 

정말 간단하다.

itertools의 product를 사용하면 repeat의 수만큼 범위 내의 모든 값의 조합을 알려준다.

예를 들어, range(1,5), repeat=3로 하면 1부터 4까지의 수(range) 중 3개(repeat)의 수들의 조합을 튜플로 만들어준다.

---

백트래킹 자체를 이해하기 좀 어려웠기 때문에 많은 문제를 풀어봐야겠다..

아직 기본 중에 기본 하나만 풀어본 거니까 앞으로 잘 이해할 수 있겠지.