[BaekJoon 15649번] N과 M(1) (Python)

N과 M(1) 문제입니다.

 

문제링크: https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

풀이

순열에 관한 문제로 nPm을 구하면 된다.

파이썬에 순열 함수를 제공하는 라이브러리가 있지만 n과 m문제는 백트래킹의 대표적인 문제로 백트래킹으로 풀었다.

중복 없이 m개의 수를 뽑아야 하므로 visited 배열을 만들어 이미 방문한 숫자면, 부모노드로 돌아가게 했다.

 

Code

 

n, m = map(int, input().split())
visited = [False] * n  # 방문 체크
result = []  # 출력

def solve(depth):
    if depth == m:  # 탈출 조건
        print(' '.join(map(str, result)))
        return
    for i in range(len(visited)):
        if not visited[i]:  # 방문 안했으면(False)
            visited[i] = True  # 방문 체크(중복 제거)
            result.append(i+1)  # 방문한 번호 입력
            #print("result1:", result)
            solve(depth+1)  # 깊이 우선 탐색
            #print("v1:",visited)
            visited[i] = False  # 깊이 방문 완료
            result.pop()  # 방문 내용 제거
            #print("result2:", result)
            #print("v2:", visited)
            #print("=======================")

solve(0)

 

 

* 참고

 

입력

4 2

 

주석 제거 후 출력

result1: [1]
result1: [1, 2]
1 2
v1: [True, True, False, False]
result2: [1]
v2: [True, False, False, False]
=======================
result1: [1, 3]
1 3
v1: [True, False, True, False]
result2: [1]
v2: [True, False, False, False]
=======================
result1: [1, 4]
1 4
v1: [True, False, False, True]
result2: [1]
v2: [True, False, False, False]
=======================
v1: [True, False, False, False]
result2: []
v2: [False, False, False, False]
=======================
result1: [2]
result1: [2, 1]
2 1
v1: [True, True, False, False]
result2: [2]
v2: [False, True, False, False]
=======================
result1: [2, 3]
2 3
v1: [False, True, True, False]
result2: [2]
v2: [False, True, False, False]
=======================
result1: [2, 4]
2 4
v1: [False, True, False, True]
result2: [2]
v2: [False, True, False, False]
=======================
v1: [False, True, False, False]
result2: []
v2: [False, False, False, False]
=======================
result1: [3]
result1: [3, 1]
3 1
v1: [True, False, True, False]
result2: [3]
v2: [False, False, True, False]
=======================
result1: [3, 2]
3 2
v1: [False, True, True, False]
result2: [3]
v2: [False, False, True, False]
=======================
result1: [3, 4]
3 4
v1: [False, False, True, True]
result2: [3]
v2: [False, False, True, False]
=======================
v1: [False, False, True, False]
result2: []
v2: [False, False, False, False]
=======================
result1: [4]
result1: [4, 1]
4 1
v1: [True, False, False, True]
result2: [4]
v2: [False, False, False, True]
=======================
result1: [4, 2]
4 2
v1: [False, True, False, True]
result2: [4]
v2: [False, False, False, True]
=======================
result1: [4, 3]
4 3
v1: [False, False, True, True]
result2: [4]
v2: [False, False, False, True]
=======================
v1: [False, False, False, True]
result2: []
v2: [False, False, False, False]
=======================

 

*Code2

n, m = map(int, input().split())
visited = [False] * (n+1)  # 방문 체크
result = [0] * (m+1)  # 출력

def solve(depth):
    if depth == m+1:  # 탈출 조건
        for i in range(1, m+1):
            print(result[i], end=' ')
        print()
    else:
        for i in range(1, n+1):
            if not visited[i]:  # 방문 안했으면(False)
                visited[i] = True  # 방문 체크(중복 제거)
                result[depth] = i  # 방문한 번호 입력 
                solve(depth+1)  # 깊이 우선 탐색 
                visited[i] = False  # 깊이 방문 완료
                result[depth] = 0 # 방문 내용 제거 

solve(1)