[알고리즘] 백준 15650 N과 M (2)

문제링크

• https://www.acmicpc.net/problem/15650

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
2. 고른 수열은 오름차순이어야 한다

주제

• 백트랙킹

난이도

• 중

백트랙킹이란,

• 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 탐색하는 알고리즘
• DFS 기반이며 보통 재귀함수를 쓴다.
• 상당한 구현력 필요..!!

풀이

import sys
# n : 숫자 범위 |  m : 수열 길이
n, m = map(int, sys.stdin.readline().split())
# 중복 접근을 방지하기위해 방문한 값을 기록해놓는 배열
# (0: 방문 X | 1:방문 O)
# n의 범위 만큼 0으로 배열을 채워준다.
visited = [0 for _ in range(n)]
# m의 길이 만큼 수열을 저장할 수 있는 스택
stack = []


def dfs(size):
    # 현재 수열을 담고있는 배열의 길이가 입력값으로 요구한 출력길이와 동일하다면 함수 종료 후 결과값 출력
    if size == m:  # 현재 m == 2
        #  배열에 '*' 추가시 대괄호없이 출력
        print(*stack)
        return

    for i in range(n):  # n이 4일시 -> 0, 1, 2, 3
        if visited[i] == 0:
            visited[i] = 1  # 중복 접근 방지를 위해 1로 변경
            stack.append(i+1)   # 수열 추가
            dfs(size + 1)   # 다음 깊이 탐색

            stack.pop()     # 탐색된 내용은 제거
            
            # visited 배열이 모두 1로 바뀌었을 때 초반에(i=0) 
            # 끝나지않은 재귀함수가 다시 호출이 되어 visited 배열을 다시 0값으로 변경한다.        
            for j in range(i+1, n):  
                visited[j] = 0

dfs(0)

풀이 방법

1. 주어진 범위만큼 반복문을 돌며 수열을 탐색한다.
2. 만약 중복된 수열이 아닐 시 스택에 추가한다.
3. 스택의 길이가 input값으로 받은 길이와 동일해질 때까지 2번을 반복하고,
4. 길이가 동일해지면 출력한다.

문제를 풀고 알게된 개념 및 소감

• 아직까진 DFS나 백트래킹, 재귀함수를 백퍼센트 이해하기는 어려운거 같다. 관련된 문제들을 더 많이 풀어보면서 공부해야겠다.