백트래킹

DFS처럼 쭉 진행하다가 더이상 진행할 필요가 없을 때는 되돌아가는 기법

백트래킹으로 순열 구현하기

진짜!!! 이해가 안되서 하나하나 자세히 적어둔다. 백준 N과 M(1) 문제의 소스코드다.

N개 중 M개를 뽑으면 되는데, 이때 M이 N이 되면 순열을 구하는거고 아니면 부분순열 구하는 것.

재귀함수로 들어가야하기때문에 반드시 종료조건을 적어주고 시작해야한다. 종료조건은 지금까지 뽑은 숫자의 개수가 M개가 될 때다. 그러면 원하는 작업을 해준 뒤(문제의 경우 출력) return해주면 된다.

N개의 숫자 배열을 전부 돌면서 M개를 뽑아야 되기 때문에 반복문으로 처음부터 끝까지 순회한다.
i번째 요소를 사용했음을 저장해야 올바른 인덱스 숫자를 가져올 수 있으므로 visited 배열을 사용하여 현재까지 어떤 인덱스가 사용되었는지 저장한다. 따라서 반복문을 시작하자마자 visited[i]가 사용되었는지 체크하고 사용되었다면 그 경우를 살펴보지 않고 넘어간다.
visited[i]를 방문 처리해준 뒤, 해당 인덱스 숫자를 배열에 넣어준다. 그런 뒤 다음 단계로 넘어갈 수 있도록 함수를 호출(재귀)한다.

여기에서 반복문을 마무리하면 1가지 경우밖에 살펴볼 수 없다. 따라서 return을 만나 호출이 끝난 뒤 되돌아오면 사용했던 요소 visited[i]를 사용 해제해주고 배열에서도 제거해줘야 모든 경우를 살펴볼 수 있다.

3개월 전에 분명 이 시리즈를 다 풀었음에도 왜 이리 새로운지. 알고리즘을 까먹지 않게 계속 유형별로 꾸준히 풀어야함을 다시 느낀다... 참고하기 좋은 유튜브를 함께 기록한다.

from sys import stdin

input = stdin.readline

N, M = map(int, input().split()) # N개 중 M개를 뽑아야 함
arr = []
visited = [False] * (N + 1)


def dfs():
    if len(arr) == M:
        print(" ".join(map(str, arr)))
        return

    for i in range(1, N + 1):
        if visited[i]:
            continue
        visited[i] = True
        arr.append(i)
        dfs()
        arr.pop()
        visited[i] = False


dfs()

실버2. 백준 10819 차이를 최대로

풀이

순열을 구하면 되는 문제다. 백트래킹 연습으로 계속 풀어보고 있다.

코드

N = int(input())
data = list(map(int, input().split()))


max_data = -int(1e9)
arr = []

visit = [False] * (N)


def dfs():
    global max_data
    if len(arr) == N:
        sum_ = 0
        for i in range(N - 1):
            sum_ += abs(arr[i] - arr[i + 1])
        max_data = max(max_data, sum_)
        return

    for i in range(N):
        if not visit[i]:
            visit[i] = True
            arr.append(data[i])
            dfs()
            visit[i] = False
            arr.pop()


dfs()
print(max_data)