[BOJ] 15649번 N과M(1) / 사용언어 : 파이썬(python)

※ 문제링크

15649번: N과 M (1)

※ 관련 알고리즘 설명

[알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset)

※ 문제풀이

# 재귀함수와 DFS를 이용한 방법
import sys
N, M = map(int, input().split()) # 입력값 받기
number_list = [x for x in range(N+1)] # 0부터 N까지의 수를 가진 숫자 리스트 생성
check_list = [False] * (N + 1) # 방문경로를 확인할 방문기록 리스트 형성
# N + 1로 형성한 이유 : 숫자 인덱스의 값을 실제 숫자와 일치화 시키기 위해서
arr_list = [] # 결과값을 입력받을 리스트 형성

def dfs(cnt): 
    if cnt == M: # 주어진 개수만큼 채워지면 출력
        # print(*arr_list) # *arr_list : arr_list내부에 있는 변수들을 공백문자를 분할기준으로 출력
        for number in arr_list: # 출력문 간소화를 위한 sys함수적용(반드시 마지막 문자는 개행문자 제거 필요)
            if arr_list == [x for x in range(N, 0, -1)]:
                if number == arr_list[-1]:
                    sys.stdout.write(f'{number}')
                else:    
                    sys.stdout.write(f'{number} ')
            elif number == arr_list[-1]:
                sys.stdout.write(f'{number}\n')
            else:
                sys.stdout.write(f'{number} ')
        # print(arr_list)
        return

    for i in range(1, N+1):
        if check_list[i]: # 백트래킹 적용
            # 설명 : 아래쪽 dfs(cnt+1)로 재귀함수를 적용할때 이미 반영된 숫자가 들어오면 재귀 중지
            # 첫번째 입력 숫자가 1이면, 두번째에 1이 들어오면 노드 탐색 중지
            # [1, 2]가 입력된 상태에서 1이나 2가 들어오면 노드탐색 중지
            # 중복된 값을 넣고 싶으면 pass로 변경
            continue
            # pass

        check_list[i] = True # 수열 체크(방문기록 작성)
        arr_list.append(number_list[i]) # 현재의 i를 기준으로 가지치기 시작, 수열 추가

        dfs(cnt+1) # +1번째 수열을 재귀

        arr_list.pop() # 수열의 마지막 자리 삭제 # 새로운 경우의 수를 찾기위해 작성한 배열 삭제
        check_list[i] = False

dfs(0)

 

# itertools를 활용한 방법
import itertools
N, M = map(int, input().split())
number_list = [x for x in range(1, N+1)]
result_list = list(itertools.permutations(number_list, M))
result_list # 출력문은 생략

 

해당문제는 DFS와 백트래킹을 활용하여 문제를 해결해야하는 기본적인 문제였다.

관련이론과 알고리즘은 다른 분들이 이미 설명을 많이 해놓으신 부분들이 있어서 참고하여 코드를 작성하였다.

코드자체를 새로 짜기보다는 이미 짜여져있는 코드를 보며 하나하나 이해하는 방식으로 학습을 진행하였다.

학습을 하면서 가장 이해가 안되었던 점은 구글링을 통해 하나하나 찾아가며 이해가 안되었던 부분들을 확인하였고,

해당 내용들을 주석을 달아서 표기해놓았다. 혹시라도 코드를 보면 같은 고민을 하는 사람들이 있다면 도움이 되었으면 한다.

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.