오늘의 알고리즘 boj -15655, 15656, 15657, 15663

문제

https://www.acmicpc.net/problem/15655
https://www.acmicpc.net/problem/15656
https://www.acmicpc.net/problem/15657
https://www.acmicpc.net/problem/15663

풀이

백트래킹으로 구하는 조합의 오름차순을 구하기 위해서는 받은 리스트를 정렬하고 백트래킹을 실행시켜주면 정렬된 형태로 나오게 된다.

백트래킹에서 수열을(조합, 순열 포함) 구하는 방법은 for문을 돌려서 특정 조건에 부합하는지 검사한 후 리스트에 넣거나 문자열에 더해서 그 값을 구하고 뎁스가 원하는 길이만큼 닿았다면 출력해주는 것으로 구할 수 있다.

특정 조건은 다양한데 visited로 방문처리 해주는 방법, idx값을 넘겨줘서 그 값보다 큰 값부터 시작하도록 하는 방법, used리스트에 들어가 있는지 in 검사를 하는 방법 등이 있는데 상황에 맞게 쓰면 된다.

boj-15655

이 문제는 idx를 넘겨줌으로써 한 번 사용된 숫자 이후부터 수열을 만들도록 하였다.

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

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

answers = []
used = []

def backtracking(depth, start):
    if depth == M:
        print(*used)
        return
        
    for idx in range(start, N):
        number = numbers[idx]
        used.append(number)
        backtracking(depth+1, idx+1)
        used.pop()
            
backtracking(0, 0)

boj-15656

이 문제는 중복되는 모든 값을 허용하므로 중복검사 없이 만들 수 있는 모든 수열을 출력하면 된다.

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

numbers = sorted(list(map(int, input().split())))
answers = []

def backtracking(depth):
    if depth == M:
        print(*answers)
        return
    
    for number in numbers:
        answers.append(number)
        backtracking(depth+1)
        answers.pop()
    
backtracking(0)

boj-15657

중복값은 허용하지만 현재 값보다 작지않은 값만을 취하는 수열을 구하는 거기 때문에 answer에 있는 마지막 값과 비교하여 현재 숫자가 크거나 같으면 재귀를 실행하는 방식으로 구했다.

현재 만들고 있는 수열에 그 값이 없다면 넣어줘야 하기 때문에 not answers 라는 조건도 같이 넣어주었다.

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

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

answers = []

def backtracking(depth):
    if depth == M:
        print(*answers)
        return
    for number in numbers:
        if not answers or (answers and answers[-1] <= number):
            answers.append(number)
            backtracking(depth+1)
            answers.pop()
        
backtracking(0)

boj-1566

이 문제는 중복값을 허용하지 않고 중복수열도 허용하지 않는다. 그러나 원래 주어진 수열에 중복 값이 존재한다면 그건 중복값 취급을 하지 않아야 한다.

그렇기 때문에 주어진 수열에서 몇번째 자리에 있는 수가 사용되었는지 확인하는 방법이 제일 효율적이라고 생각해서 visited 리스트를 만들어 방문체크를 하고 길이가 충족된 수열이 만들어지면 중복된 값을 제거하는 set 자료형에 넣어 중복을 제거해주고 사전순 출력을 위해서 마지막으로 정렬을 해주고 출력해주면 값을 구할 수 있다.

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

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

answers = set()
used = []
visited = [0] * N

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