백준 15649 N과M(1) 파이썬

백준 15649번 N과 M(1) 풀이

접근방식

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())

# m개의 숫자가 채워질 리스트 선언
arr = []

# 방문 여부를 확인하는 리스트
# n+1 로 한 이유는 n이 1부터 시작하기 때문에 인덱스를 맞추기 편하다.
visited = [False for _ in range(n+1)]

# dfs 함수 선언
def dfs(depth, n, m):
  # 만약 depth == m 이라면 공백을 두고 출력
    if depth == m:
        print(' '.join(map(str, arr)))
    
    for i in range(1, n+1):
      # 방문하지 않았다면
        if not visited[i]:
          # 방문한 것으로 처리해주고
          # 자연스럽게 arr에 append 시킨다.
            visited[i] = True
            arr.append(i)
          # 재귀함수로 depth에 1을 추가해주고 다시 한번 dfs를 수행한다.
            dfs(depth+1, n, m)
          # 재귀함수로 보낸 것과 별개로 방금 처리한 i는 다시 방문하지 않을 것으로 바꿔준다.
            visited[i] = False
          # 그리고 pop을 시켜서 arr은 다시 비워둔다.
          # 그 전에 저장한 i의 경우 이미 재귀함수로 dfs로 전달되었다.
            arr.pop()


dfs(0, n, m)

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

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

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

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

Just do it & Keep steady