BOJ 15649 N과 M (1)

김재섭·2021년 3월 31일

BOJ 15649 백준 백준 15649 백준 N과 M (1)

백준

목록 보기

3/10

문제

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

아이디어

모든 permutation을 뽑아서 출력하면 된다.
DFS로 permutation을 만들어서 출력한다.
코딩테스트에서 외부 라이브러리를 못쓰는 경우가 자주 있으므로, itertools를 사용하지 않음

코드

N, M = map(int, input().split())

def func(depth, lst):
    if depth == M-1:
        print(*lst)
        return

    for i in range(1, N+1):
        if i not in lst:
            lst[depth+1] = i # 다음 depth 노드에 값 대입
            func(depth+1, lst)
            lst[depth+1] = 0 # 이미 자식노드에 방문하고 부모노드로 다시 올라왔기 때문에 노드에 값 제거

for i in range(1, N+1):
    arr = [0 for _ in range(1, M+1)]

    arr[0] = i 
    func(0, arr)