백준 15650 N과M(2) 파이썬

백준 15650번 N과 M(2) 풀이

접근방식

1. m개의 숫자가 채워질 리스트(arr)를 생성한다.
2. 방문한 숫자를 체크해줄 visited 리스트를 생성한다.
3. dfs 라는 함수를 만들어서 재귀함수를 활용하여 depth를 계산한다.
4. depth == m이라면 arr 리스트에 저장된 숫자를 출력하도록 한다.

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

n, m = map(int, input().split())
# 방문처리 리스트 초기화
visited = [False for _ in range(n)]
# 길이만큼 저장할 임시 리스트 생성
arr = []

def dfs(start, depth):
    if depth == m:
        print(' '.join(map(str, arr)))
    for i in range(start, n):
        if not visited[i]:
            visited[i] = True
            arr.append(i+1)
            # N과M(1)과 다른 부분은 이 부분입니다.
            # 이전에 저장된 수보다 큰 수를 저장하기 때문에 직전의 i+1을 해줍니다.
            # 그 결과로, depth가 m이 아닐 경우, arr에 저장된 수보다 큰 수만 저장됩니다.
            dfs(i+1, depth+1)
            visited[i] = False
            arr.pop()
dfs(0,0)

해당 문제는 실버3레벨에 해당하므로 어렵지 않게 풀 수 있는 문제였습니다.

백트래킹과 재귀함수를 입문하기에 최적의 문제집이라고 생각해서

N과M 시리즈를 꼭 여러번 풀어보시는 것을 추천드립니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.

Just do it & Keep steady