[BOJ] 15666 : N과 M (12) [백트랙킹](Python)

문제 링크

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

15666번: N과 M (12)

소스 코드

def main():
    n,m = map(int,input().split())
    # 오름차순 정렬(중복 제거)
    nums = sorted(list(set(list(map(int,input().split())))))
    answers= []

    def dfs(arr):
        if len(arr) == m: # 길이가 m이면 종료
            answers.append(arr[:])
            return
        
        for idx in range(len(nums)):
            # 배열이 비어있거나 마지막 숫자 이상인 경우에만
            if not arr or arr[-1] <= nums[idx]:
                arr.append(nums[idx])
                dfs(arr)
                arr.pop()

    dfs([])

    for answer in answers:
        print(*answer)

if __name__ == '__main__':
    main()

 

해설

• 백트랙킹, DFS

벌써 몇 번째 N과 M인지 모르겠네요.. ㅋㅋㅋ

이제 확실히 백트랙킹 기본 유형은 어떻게 조건을 세팅하면 될지 감이 옵니다 💪🏻

 

숫자 리스트 중복 없이 입력 받기

어차피 최종적으로 출력해야 하는 것들은 값이 점점 커지는 형태이기 때문에 오름차순을 적용하면 편하겠죠.

이 문제의 독특한 점은 같은 숫자가 여러 개 반복되어도 상관 없다는 것입니다.

따라서 같은 숫자가 여러 개 주어지는 경우 그냥 한 개로 압축시키는 것이 낫습니다.

nums = sorted(list(set(list(map(int,input().split())))))

 

만약 같은 숫자가 여러 개 존재한다면 이를 나중에 백트랙킹하는 과정에서 중복된 배열을 추가로 생성하기 때문입니다.

([1,1,1,2] 라는 배열이 주어졌을 때 결과가 어떻게 될지 상상해보세요 🤔)

 

백트랙킹

종료 조건은 간단합니다.

m개를 뽑아 수열을 만드는 것이므로, 지금 확인하는 배열의 길이가 m인 경우 종료하도록 합니다.

이때 리스트를 (깊은)복사해서 추가해야 재귀함수들이 종료되는 과정에서 동일한 리스트(전부 공백이 됩니다)가 추가되는 것을 방지할 수 있습니다.

if len(arr) == m: # 길이가 m이면 종료
    answers.append(arr[:])
    return

 

배열에 숫자를 추가할 때는 두 가지만 고려하면 됩니다.

배열이 비어있지 않아야 하고, 기존에 들어있던 가장 마지막 숫자 이상의 숫자만 넣을 수 있습니다.

따라서 두 조건을 or 논리 연산자를 통해 엮어 줍니다.

이후는 일반적인 백트랙킹과 동일하게 '리스트에 값 추가' -> '재귀' -> '리스트 값 pop' 을 실행하면 됩니다.

for idx in range(len(nums)):
    # 배열이 비어있거나 마지막 숫자 이상인 경우에만
    if not arr or arr[-1] <= nums[idx]:
        arr.append(nums[idx])
        dfs(arr)
        arr.pop()

 

answers 리스트에 저장된 정답들은 리스트로 담겨있으므로 이를 전부 풀어서 출력하도록 하면 정답입니다.