백준 15650번 파이썬 문제풀이(브루트 포스 - N과M(2))

 

코드1 (인덱스 이용x)

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

array = [x for x in range(1, n + 1)]
result = []
out = []
visited = [False] * n


def solve(depth, n, m):
    if depth == m:
        out_str = sorted(out)  # out값들을 정렬해서 out_str 리스트에 넣는다.
        if out_str not in result:  # 만약 result에 out_str값이 존재하지 않는다면
            result.append(out_str)  # 그 값을 result에 추가
        return
    for i in range(depth, n):
        if not visited[i]:
            visited[i] = True
            out.append(i + 1)
            solve(depth + 1, n, m)
            visited[i] = False
            out.pop()


solve(0, n, m)

for i in result:
    print(' '.join(map(str, i)))

-> 단순히 순열을 구하는 재귀 코드에서 새로운 리스트에 출력을 위한 out리스트의 값을 오름차순으로 정렬 해서 그 원소가 중복되지 않는 다면 새로운 result 리스트에 대입한다. 그리고 마지막에 result의 원소들을 출력하는 방식으로 해결했다. 

 

단 위의 코드는 불필요한 result 리스트와 append메서드 그리고 정렬을 위한 sorted메서드 까지 사용하기 때문에 시간적,공간적 측면에서 불리하다. 따라서 인덱스를 이용하면 쉽게 해결할 수 있다.

 

코드2(인덱스 이용)

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

out = []
visited = [False] * (n + 1)


def solve(depth, idx, n, m):
    if depth == m:
        print(' '.join(map(str, out)))
        return
    for i in range(idx, n + 1):
        if not visited[i]:
            visited[i] = True
            out.append(i)
            solve(depth + 1, i + 1, n, m)
            visited[i] = False
            out.pop()


solve(0, 1, n, m)

-> 다음과 같이 index값을 받아서 넘겨주면 쉽게 해결이 가능하다.