[백준] [Python] N과 M(2) - 백트래킹

www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

 

 

 

Python

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

arr = [0]*(n+1)
visit = [0]*(m)
result = []

def backtracking(k):
    if (k == m):
        x = arr[:m]
        x.sort()
        if x not in result:
            result.append(x)
        return
    for i in range(1, n+1):
        if visit[i] == 0:
            arr[k] = i
            visit[i] = 1
            #print(visit, arr)
            backtracking(k+1)
            visit[i] = 0
            #print(visit, arr)
            
            
backtracking(0)

for x in result:
    for i in range(m):
        print(x[i], end=" ")
    print()

 

 

 

 

짧은 풀이

• 15649번과 다른 점은 중복되는 경우를 제외해야 하기에 해당 부분이 result 리스트에 없을 때만 추가한다.
• 왼쪽은 visit, 오른쪽은 arr 리스트다.
  • visit 리스트는 인덱스 번호와 같은 곳에 1을 넣음으로써 해당 숫자가 현재 포함된 숫자인지 알려준다.
    • visit과 arr 둘 다 n+1개 만큼 필요하다
  • visit의 1의 개수 == m 일 때만 출력해야 한다.
  • arr리스트 전체가 아닌 처음부터 m개까지만 필요하기에 arr[:m]만큼 슬라이싱한 후 정렬하였다.