백준 - 15652번 N과 M (4) python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

🔷 알고리즘 분류 - 백트래킹, 난이도 - 실버 3

 

백트래킹(Backtracking) 알고리즘은 결정해야 하는 여러 개의 선택지가 있고, 이 중에서 최적의 해결책을 찾아내야 하는 문제들에 대해 사용됩니다. 이 알고리즘은 모든 가능한 경로를 탐색하되, 어떤 경로가 해결책으로 이어질 것 같지 않으면 그 경로를 더 이상 탐색하지 않고 다른 경로를 탐색하는 방식으로 동작합니다.

이런 방식을 통해 불필요한 계산을 줄이고 탐색의 효율성을 높일 수 있습니다. 이를 위해 백트래킹 알고리즘은 주로 재귀 함수를 이용해 구현되며, 일반적으로 DFS(깊이 우선 탐색) 방식을 사용합니다.

예를 들어, 스도쿠 문제를 백트래킹으로 해결한다고 가정해 봅시다. 스도쿠 문제는 빈칸을 1부터 9까지의 숫자로 채우는 문제인데, 이때 각 행, 각 열, 그리고 3x3 크기의 작은 사각형에 1부터 9까지의 숫자가 중복 없이 들어가야 합니다.

백트래킹을 이용하면 빈 칸에 1부터 9까지 숫자를 하나씩 넣어보면서 진행합니다. 만약 어떤 숫자를 넣었을 때 규칙에 어긋나게 된다면, 그 숫자를 빼고 다음 숫자를 넣어보는 과정을 반복합니다. 이렇게 해서 모든 빈칸을 규칙에 맞게 채울 수 있으면 문제의 해결책을 찾은 것이고, 그렇지 않다면 다른 경로를 탐색합니다.

백트래킹 알고리즘은 이렇게 가능한 모든 경로를 체계적으로 탐색하되, 해결책이 될 수 없다는 것이 밝혀진 즉시 그 경로는 포기하고 다른 경로를 탐색하는 방식을 사용합니다. 이를 통해 불필요한 계산을 줄이고, 효율적으로 문제를 해결할 수 있습니다.

 

🔶첫 번째 풀이 - 재귀(def backtracking)를 이용한 풀이

 

# 백트래킹 함수를 정의합니다.
def backtracking(n, m, result, start):
    # result의 길이가 m과 같다면(즉, m개를 모두 선택했다면)
    if len(result) == m:
        # result를 출력합니다. 각 요소는 공백으로 구분됩니다.
        print(' '.join(map(str, result)))
        # 함수를 종료합니다.
        return
    
    # start부터 n까지의 모든 수에 대하여
    for i in range(start, n+1):
        # 현재의 수 i를 result에 추가합니다.
        result.append(i)
        # 다음 수를 선택하러 재귀 호출합니다. 이때, 다음 수는 현재의 수 이상이어야 합니다.
        backtracking(n, m, result, i) #i=1이라면 1~4까지 돌고서 i값이 1증가 후 재귀문 반복
        # 백트래킹을 위해, 방금 추가한 수 i를 제거합니다.
        result.pop()

# n과 m을 입력받습니다.
n, m = map(int, input().split())
# 선택된 수를 저장할 리스트를 초기화합니다.
result = []
# 백트래킹을 시작합니다. 이때, 처음 선택할 수는 1이상이어야 합니다.
backtracking(n, m, result, 1)

 

🔶두 번째 풀이 - 파이썬의 내장 모듈인 itertools의 combinations 함수 이용

 

- itertools 라이브러리의 combinations 함수를 사용하여 같은 문제를 풀 수 있습니다.

combinations 함수는 입력받은 반복 가능한 데이터에서 일부를 선택하는 모든 경우를 반환합니다.

 

from itertools import combinations

n, m = map(int, input().split())

for numbers in combinations(range(1, n+1), m):
  print(' '.join(map(str, numbers)))

 

🔶 초보자를 위한 코드풀이

- print(' '. join(map(str, result)))

 

result = [1, 2, 3, 4, 5]

# map 함수를 이용해 결과 리스트의 모든 원소를 문자열로 변환
result_as_str = map(str, result)

# join 함수를 이용해 결과 리스트의 모든 원소를 공백으로 연결
result_joined = ' '.join(result_as_str)

print(result_joined)  # 출력: 1 2 3 4 5

 

 

위 풀이 중 참고하여 알고리즘 공부에 도움 되셨으면 좋겠습니다.

 

🤗파이팅입니다~ 여러분!!🤗