문제 정보
https://www.acmicpc.net/problem/15649
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
접근방법
1.백트래킹을 1도 모르니까 강의를 듣고 문제에 접근해보자
전형적인 백트래킹 문제라고 하는데 백트레킹에 대해 잘 알지 못한다.
유튜브에서 강의를 듣고 백트래킹에 대해 간략하게 이해한 후 문제를 풀었다.
2.어떻게 가지를 쳐야할까?
백트래킹의 핵심은 모든 경우를 다 탐색하지 않는 것이라고 알고있다.
어떻게 조건을 만족시키면 다음으로 넘어갈지 생각해보자
풀이
def BT(makenum):
if M == len(makenum):
print(*makenum)
return
else:
for num in nums:
if num in makenum:
continue
else:
makenum.append(num)
BT(makenum)
makenum.pop()
N, M = map(int, input().split())
nums = [1 + i for i in range(N)]
makenum = []
# dap = []
# # idx = 0
BT(makenum)
메인 부분에서 입력을 받고
1~n 까지의 숫자를 미리 만들어주고 시작했다.
BT 함수를 작성했다.
if M == len(makenum):
print(*makenum)
return
조건을 만족하면 출력 후 함수 대기위치(??) 로 돌아갈 수 있게 해 주었다.
else:
for num in nums:
if num in makenum:
continue
else:
makenum.append(num)
BT(makenum)
makenum.pop()
조건을 만족하지 못하면 이쪽으로 와서 코드를 실행한다.
1~n 까지의 숫자가 있는 nums을 num 으로 쪼갠다
만약 리스트에 담겨있는 숫자와 num 이 같으면 무시한다.
그게 아니면 현재 num 을 리스트에 담고 다시 BT 함수를 호출한다.
이렇게 되면 같은 새로운 함수이기 때문에 for를 처음부터 돌아서 num이 1부터 시작하게 되지만
담겨있는 숫자와 현재 담으려는 숫자가 같으면 무시하는 조건이 있기 때문에 그 다음 for 문으로 넘어가게 된다.
EX) makenum = [1] num 1 => 무시 하고 num 2 로 바뀐다.
그리고 숫자를 넣고 다시 BT 함수를 호출한다
이렇게 반복해서 호출이 되고 makenum의 길이와 m이 같아졌을 때 makenum 을 프린트 해주고
함수가 대기하고 있는 위치(??)로 돌아가서 뒤에오는 숫자를 pop 해준다.
느낀점
스터디에서 풀기로 한 문제였다. 개인적으로 아직 BFS 나 DFS 심지어는 브루트포스 같은 알고리즘도
제대로 알지 못하는 상황이여서 백트래킹이 너무나도 어렵게 느껴졌다.
유튜브 코드없는 프로그래밍 님의 강의를 듣고, 디버거로 코드를 돌려보고
같은 문제를 풀기위해 코드를 직접 작성해 보면서 어느정도 이해하고 문제를 풀었다.
하지만 백트래킹을 정확하게 알지 못하기 때문에 과연 이게 백트래킹일까? 하는 의문은 남는다.
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 15649 N과 M (4) (파이썬) (0) | 2022.09.07 |
---|---|
백준 15649 N과 M (2) (파이썬) (0) | 2022.09.06 |
백준 2667 단지번호붙이기(파이썬) (0) | 2022.09.04 |
백준 7576 토마토(파이썬) (0) | 2022.09.02 |
백준 2477 참외밭(파이썬) (0) | 2022.08.25 |