[BOJ] 15649. N과 M (1)

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

15649번: N과 M (1)

 

1. 해결방법

"""
### 백트래킹 ###
- 1부터 N중에 하나를 선택.
- 다음 1부터 N을 선책할 때 이미 선택한 값이 아닌경우를 선택 > 방문여부
- M개를 선택할 경우 프린트

- 중복이 가능한 경우 : N^N : N = 8까지 가능
- 중복이 불가능한 경우 : N! : N = 10까지 가능
- 시간복잡도가 2억이 넘지 않아야 한다. (1초에 2억개 연산 python)

1. 아이디어
- 백트래킹 재귀함수 안에서, for문 돌면서 숫자 선택 (방문여부 확인해야함)
- 재귀함수에서 M개를 선택할 경우 print

2. 시간복잡도
- N! : 가능 (문제의 N이 자연수 8까지)

3. 자료구조
- 방문 여부 : bool[][]
- 선택한 값 입력 배열 : int[]
"""

 

 

2. 정답코드

 

입력 예제(1)

3 1

출력 예제(1)

1
2
3

 

입력 예제(2)

4 2

출력 예제(2)

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
# 결과
result = []
# 방문
chk = [False] * (n + 1)


# recur
def recur(num):
    # 재귀 끝낼 지점
    if num == m:
        print(' '.join(map(str, result)))
        return

    # 재귀
    for i in range(1, n + 1):
        if chk[i] == False:
            chk[i] = True
            result.append(i)
            recur(num + 1)
            chk[i] = False
            result.pop()


# main
recur(0)