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

※ 문제링크

15651번: N과 M (3)

※ 기본문제

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

※ 문제풀이

import sys
N, M = map(int, input().split())
# N, M = map(int, sys.stdin.readline().split()) # 입력받을 값들이 다량일때 input보다 효과적
number_list = [x for x in range(1, N+1)] # 1부터 N까지의 값들로 이루어진 리스트 생성
arr_list = [] # 결과값을 작성하고 출력할 리스트 생성

def dfs():
    if len(arr_list) == M:
        # print를 사용해서 결과값 출력
        # print(*arr_list) 
        # sys를 사용해서 결과값 출력
        if arr_list == [N for _ in range(M)]:
            for i in range(M):
                if i == M-1:
                    sys.stdout.write(f'{arr_list[i]}')
                else:
                    sys.stdout.write(f'{arr_list[i]} ')
        else:
            for i in range(M):
                if i == M-1:
                    sys.stdout.write(f'{arr_list[i]}\n')
                else:
                    sys.stdout.write(f'{arr_list[i]} ')
        return

    for i in range(0, N):
        arr_list.append(i+1)
        dfs()
        arr_list.pop()

dfs()

 

해당문제는 BOJ 15649번에서 조금만 변형된 형태로 자기자신또한 포함하여 순열을 작성하는 것이 핵심인 문제였다. 15649번에서는 작성한 숫자들의 방문기록을 작성하여 특정수가 2번이상 들어가지 않게 했다면 해당 문제에서는 중복되는 경우까지 답으로 출력해야하는 문제였다. 문제를 풀면서 해당문제에 백트래킹의 개념이 어떻게 적용되는지 정확히 이해가 되지 않았으며, 단순하게 모든 경우의 수를 탐색하는 브루스포트 알고리즘과 단순 DFS만으로도 풀 수 있다고 생각하여 모든 경우의 수를 탐색하여 출력하는 형태로 코드를 작성했다. 방문기록을 작성할 필요가 없다고 생각하여 메모리 및 시간 단축을 위해 방문기록을 작성할 리스트는 따로 작성하지 않았으며, 입력받은 M의 값과 출력해야하는 결과값을 저장하는 리스트의 길이가 같아질때 출력하고 함수 실행을 멈추도록 작성하였다.

 

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