[백준 15649번] N과 M(1)

15649번: N과 M (1)

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

is_used = [False]*9

temp = []

answer = []

def backtracking():
    
    if len(temp) == m:
        answer.append(' '.join(map(str,temp)))
        return
    for i in range(1,n+1):
        if not is_used[i]:
            is_used[i] = True
            temp.append(i)
            backtracking()
            is_used[i]= False
            temp.pop()

backtracking()   

for ans in answer:
    print(ans)

 

import sys

input = sys.stdin.readline

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

# 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

answer = []

visited = [False]*(n+1)

def dfs(numbers):
    
    if len(numbers) == m:
        answer.append(numbers)
        return
    
    for i in range(1,n+1):
        if not visited[i]:
            visited[i] = True
            dfs(numbers+[i])
            visited[i] = False

dfs([])

for ans in answer:
    for n in ans:
        print(n,end=" ")
    print()

👉🏻 2024.06.30 재풀이 코드

 

이번 문제는 1부터 N까지의 수 중에서  중복된 원소가 없이 M개를 골랐을 때 나올 수 있는 모든 경우의 수를 구하는 문제이다. 즉, 쉽게 말하면 1부터 N까지의 수 중에서 원소 M개를 가진 '순열의 개수'를 구하는 문제이다.

 

물론 'from itertools import permutations'로 라이브러리를 활용하여 풀 수도 있겠지만, 이 문제의 의도는 "Backtracking"이다.

 

백트래킹 알고리즘은 모든 경우의 수를 모두 탐색하는 것이 아니라 불필요한 경로를 사전에 차단한다. 이 문제에서는 is_used(visited) 리스트로 이미 사용했는지 여부를 사전에 확인하여 이미 사용한 원소의 경우에는 탐색을 하지 않는 방식으로 가지치기(Pruning)를 해주었다.

 

배운 점 및 느낀 점

1. DFS/BFS와 백트래킹 알고리즘의 차이점은 백트래킹은 '모든 경우의 수를 탐색하는 과정에서 조건문이나 리턴문을 걸어 답이 절대 될 수 없는, 즉 유망하지 않는 경우를 사전에 차단한다는 것'이다.
2. DFS/BFS와 백트래킹 모두 탐색을 한 뒤 이전으로 돌아가는 과정을 거친다. 다만 차이점은 백트래킹은 마지막 노드까지 도달하기 전에 가능성이 없다고 판단되었을 때 바로 이전으로 돌아간다는 것이다. ⭐️