오늘의 알고리즘 boj -15664, 15665, 15666

문제

https://www.acmicpc.net/problem/15664
https://www.acmicpc.net/problem/15665
https://www.acmicpc.net/problem/15666

N과 M 시리즈 문제는 백트래킹 코드를 손에 익숙하게 하기에 딱 좋은 예제라고 생각한다.

문제에서 요구하는 바를 어떻게 충족시킬지 생각해보면서 하나씩 정복해나가기를 추천한다.

풀이

boj-15664

비 내림차순검사와 중복검사를 해야한다. 지난번에 긴 조건문이 마음에 들지 않아서 이번에는 -1이 초기값으로 들어가 있는 리스트를 인자로 받아서 굳이 값이 있는지 없는지 검사하는 로직을 빼주었다. 마지막에 슬라이싱으로 [1:] 처리를 해주면 간단하게 제일 앞 -1 값을 빼줄 수 있기 때문에 코드가 좀 더 간결해진 것 같다.

N, M = map(int , input().split())

numbers = list(map(int, input().split()))

visited = [False] * N

answers = set()
def backtracking(depth, sequential):
    if depth == M:
        answers.add(tuple(sequential[1:]))
        return
    
    for idx in range(N):
        if not visited[idx] and sequential[-1] <= numbers[idx]:
            visited[idx] = True
            backtracking(depth+1, sequential + [numbers[idx]])
            visited[idx] = False
            
            
backtracking(0, [-1])
for answer in sorted(answers):
    print(*answer)

boj-15665

같은 수를 골라도 되고 중복수열만 없도록 하는 문제다.
set을 통해 중복수열을 제거해주고 나머지는 visited 같이 중복을 검사할 수단은 필요하지 않고 for문에 그대로 재귀를 실행해주면 된다.

N, M = map(int, input().split())

numbers = list(map(int, input().split()))

answers = set()

def backtracking(depth, sequential):
    if depth == M:
        answers.add(tuple(sequential))
        return
    
    for number in numbers:
        backtracking(depth+1, sequential + [number])

backtracking(0, [])
for answer in sorted(answers):
    print(*answer)

boj-15666

시퀀셜에 미리 -1값을 초기값으로 넣어 비내림차순 검사를 쉽게 할 수 있게 만들었다.

그리고 중복된 값을 허용하기 때문에 다른 조건 없이 재귀함수를 실행해준다.

중복된 수열을 허용하지 않기 때문에 set자료구조를 통해서 중복수열을 제거해주고 마지막으로 사전순으로 출력하기 위해 정렬을 하고 하나씩 뽑아 출력해준다.

N, M = map(int, input().split())

numbers = list(map(int , input().split()))

answers = set()

def backtracking(depth, sequential):
    if depth == M:
        answers.add(tuple(sequential[1:]))
        return
    
    for number in numbers:
        if sequential[-1] <= number:
            backtracking(depth+1, sequential+ [number])
            
backtracking(0, [-1])

for answer in sorted(answers):
    print(*answer)