백준,N과 M (1),15649

[유형]

백트래킹

 

[문제링크]

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

 

[요약]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

[문제풀이]

백트래킹이란?
알고리즘 기법 중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한조건에 위배되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 상태로 넘어간다. 더 이상 탐색할 필요가 없는 상태가 제외한다는 것인데, 이를 가지치기라고 한다.

 

백트래킹 특성에서 조건에 부합하지 않으면 이전 수행으로 돌아가야 함으로 BFS보다는 DFS이 구현하기 더 편하기 때문에 주로 DFS를 사용한다. DFS와의 차이점은 가지치기를 한다는 점이다.

조건: 이미 방문한 경우라면 제외시키면 된다.

import sys
def input():
    return sys.stdin.readline().rstrip()

def dfs(lst):
    # 종료조건
    if len(lst) == M:
        ans.append(lst)
        return

    for j in range(1,N+1):
        if v[j]==0:
            v[j] = 1
            dfs(lst+[j])
            v[j] = 0

N, M = map(int, input().split())
ans = []
v = [0] * (N+1)

dfs([])

for lst in ans:
    print(*lst)

[참고] https://velog.io/@gayeong39/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BackTracking

https://velog.io/@yusuk6185/%EB%B0%B1%EC%A4%80-15649-N%EA%B3%BC-M-1-%ED%8C%8C%EC%9D%B4%EC%8D%AC-with-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9