[정올] 주사위 던지기1

기본적인 DFS로 구현하는 
중복순열, 조합, 순열을 만드는 문제이다.
이 3가지 기능은 완전탐색을 요구하는 경우 많이 사용하기 때문에 필수적으로 구현할 수 있어야하고 또
빠른 시간 내에 구현할 수 있어야한다.

 

풀이

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

path = [0 for _ in range(N)]
used = [0 for _ in range(7)]
def run1(lev):
    if lev == N:
        print(*path)
        return

    for i in range(1, 7):
        path[lev] = i
        run1(lev+1)

def run2(lev, start):
    if lev == N:
        print(*path)
        return

    for i in range(start, 7):
        path[lev] = i
        run2(lev+1, i)

def run3(lev):
    if lev == N:
        print(*path)
        return

    for i in range(1, 7):
        if used[i] == 1:
            continue
        used[i] = 1
        path[lev] = i
        run3(lev + 1)
        used[i] = 0

if M == 1:
    run1(0)
elif M == 2:
    run2(0, 1)
elif M == 3:
    run3(0)

run을 3가지로 나눠서 구현하였다.

입력 받은 N, M을 이용하여 N은 주사위의 갯수 M은 어떤 기능을 수행할 것인지 정하면 된다.

1번 기능인 중복 순열은 주사위 1 ~ 6까지 모든 분기를 이용하여 구현하는 가장 기본적인 완전탐색이다.
2번 기능인 조합은 start라는 값을 이용하여 앞에서 사용했던 분기 이상의 숫자만 사용한다.
3번 기능인 순열은 1번 기능에서 used 리스트를 이용하여 중복이 나오지 않게 구현하였다.

기본적 코드에 자주 사용했던 부분이지만 다른 문제들과 합쳐져 많이 등장하기 때문에 for문 print문 사용하듯이
사용할 수 있게 연습해두는 것이 좋을 것 같다.