백준 / N과 M (10) / 15664번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: N과 M (10) / 15664번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/15664

 

문제 설명

---

나의 풀이

def dfs(level, start):
    prev_num = 0
    if level == m:
        print(*result)
        return
    for i in range(start, n):
        if not visited[i] and nums[i] != prev_num:
            visited[i] = True
            result[level] = nums[i]
            prev_num = nums[i]
            dfs(level + 1, i + 1)
            visited[i] = False


if __name__ == "__main__":
    n, m = map(int, input().split())
    nums = sorted(map(int, input().split()))
    visited = [False] * n
    result = [0] * m
    dfs(0, 0)

---

※ 알아야 할 것

def dfs(n, m, sequence, result, start):
    if len(result) == m:
        print(' '.join(map(str, result)))
        return

    prev = 0  # 이전에 선택한 값을 추적하기 위한 변수
    for i in range(start, n):
        # 이전에 같은 레벨에서 같은 값을 사용했다면 건너뛰기
        if prev == sequence[i]:
            continue

        result.append(sequence[i])
        dfs(n, m, sequence, result, i)  # 비내림차순을 위해 i부터 시작
        result.pop()
        prev = sequence[i]  # 현재 값을 이전 값으로 설정

항목방식 (prev 방식)과 visited 방식 위의 방식의 문제를 해결한 풀이 방법을 사용했습니다!

중복 제거 시점	수열 출력 직전에 prev로 중복 필터링	수 선택 자체를 제한하여 중복 방지
같은 수 재사용	허용됨 (dfs(level, i))	불가능 (visited[i]로 차단)
비내림차순 유지	dfs(level, i)	dfs(level, i + 1)
성능	비교적 간단하나 중복 수열 DFS를 탐색함	중복 경로 자체를 차단하여 더 효율적
문제 유형	중복 조합에 가까움	조합 문제에 적합