[BOJ] 15654번 N과 M(5) / 사용언어 : 파이썬(python)

※ 문제링크

15654번: N과 M (5)

해당 문제는 백트래킹과 관련된 문제로 DFS를 활용한 재귀를 통해 해결할 수 있는 문제였다. 백트래킹의 기본적인 원리를 구현할 수 있다면 쉽게 해결할 수 있었고, 중복을 허용하지 않고, 숫자가 같아도 순서가 다르면 다르다는 점을 고려하여 해결하면 되는 문제였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 리스트에 저장하고, 오름차순으로 정렬해준다.

2. 숫자들의 순열조합을 작성할 DFS함수를 백트래킹을 적용해서 작성하고, 조건 만족시 값을 출력해주는 함수를 작성한다.

 

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
numbers.sort()
visited = [False for _ in range(N)]
arr = []
def dfs():
    if len(arr) == M:
        print(*arr)
        return
    for i in range(N):
        if visited[i]:
            continue

        visited[i] = True
        arr.append(numbers[i])
        dfs()
        arr.pop()
        visited[i] = False
dfs()

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.