[BOJ][Python] 15649 N과 M(1)

[문제]

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

15649번: N과 M (1)

 

[코드]

1. 재귀를 사용해서 백트래킹 알고리즘 구현

#dfs // n = 3, m = 1 인 경우 코드 실행 순서 
x = []
def backtracking():		#5 14 23
    if len(x) == m:		#6 15 24
        print(*x)		#7 16 25
        return 			#8 17 26
    
    for i in range(1, n+1): 	#1 10 19
        if i not in x:		#2 11 20
            x.append(i)		#3 12 21
            backtracking()	#4 13 22
            x.pop()		#9 18 27
            
#출력
#7: 1
#16: 2
#25: 3

 

if i no in x: 라인에서 x에 있는지 x 리스트를 전부 돌아서 시간이 걸린다. 

 

1-1. 재귀를 사용해서 백트래킹 알고리즘 구현 - 방문했는지 확인하는 배열 추가 

    for i in range(1, n+1):
        if visit[i]:
            continue
        visit[i] = True
        x.append(i)
        backtracking()
        x.pop()
        visit[i] = False

 

- 방문했으면 continue

- pop 하면서 방문 값을 다시 False로 돌려준다. 

- False로 돌려주지 않으면 모든 경우의 수가 출력되지 않는다.

ex) n = 4, m = 2 일 때, 출력 >> 1, 2 / 1, 3 / 1, 4 

 

1. 최종 코드(main 포함)

#S3_15649 N과 M(1).py

#dfs
x = []
def backtracking():
    if len(x) == m:
        print(*x)
        return 
    
    for i in range(1, n+1):
        if visit[i]:
            continue
        visit[i] = True
        x.append(i)
        backtracking()
        x.pop()
        visit[i] = False
        
#main
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
visit = [False] * (n+1)
backtracking()

 

2. permutations 함수 사용 (순열)

- 파이썬에서는 순열 함수로 쉽게 구할 수 있다. 

import sys
input = sys.stdin.readline

from itertools import permutations as p

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

arr = [i for i in range(1,n+1)]
x = list(p(arr,m))

for i in x:
    print(*i)