코드

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

visited = [False] * (n+1)
answer = []

# 백트래킹은 dfs의 일종
def dfs(depth):
    
    # 1부터 n까지의 수열만 구하므로
    # depth가 0이 될 때 탈출시키면 됨 
    # 이 과정은 매번 재귀마다 실행됨
    if depth == 0:
#         print(answer)

        # join은 list의 요소가 문자열인 경우에만 사용 가능
        # 따라서 map과 str 메소드를 이용하여 answer list의 요소를 모두 문자열로 바꿔주고
        # join 연산을 활용하여 결과를 출력
        print(" ".join(map(str, answer)))
        return
    
    # 1부터 n까지 반복 실행
    for i in range(1, n+1):
        
        # i가 방문하지 않은 요소라면
        # 즉, i로 시작하는 수열을 구하지 않은 상태라면
        if not visited[i]:
            
            # answer 리스트에 i값을 더함
            # i부터 시작하는 m만큼 길이의 수열을 구할 것이므로
            # 일단 i를 넣어준다
            answer.append(i)
            
            # i를 방문처리 함
            visited[i] = True
            
            # depth를 1 줄이고 dfs를 재귀적으로 호출
            # 이 경우, 재귀적으로 호출된 dfs의 경우에
            # 이번에 처리한 i는 방문처리가 완료됐으므로 (True)
            # i는 i+1로 넘어감 => 재귀적 호출인 경우에도 i는 어차피 방문처리가 완료돼있으므로
            # 조건문이 실행되지 않음
            # 문제에서 m의 길이인 수열을 구하는 것이므로
            # depth는 사실상 m이고
            # m이 0이 되는 경우 answer의 요소들을 출력하므로
            # 결국 길이가 m인 수열이 완성되어 출력하게 된다
            dfs(depth-1)
            
            # 여기까지 내려왔다는 것은
            # dfs의 재귀적 호출이 일단 종료됐다는 의미
            # 이 경우, answer에 있는 맨 마지막 요소를 삭제하고
            # i의 방문처리를 false로 바꿔준다
            # => 바로 전 재귀적 호출을 한 dfs에서 i를 방문처리 한 채로 동작하면 원하는 결과가 나오지 않음
            answer.pop()
            visited[i] = False

dfs(m)

문제 해설

백트래킹 알고리즘 문제.

백트래킹 알고리즘을 처음 접하여 기본 개념을 구글링을 통해 공부한 후, 나름대로 주석을 달아가며 문제를 여러번 반복해서 풀어보았다. 백준 자체적으로 위의 문제의 변형 문제로 총 4문제를 백트래킹 기본 문제로 등록돼있어 모두 풀어보며 연습을 하였다.

기본적으로 DFS를 이용하여 문제에 접근했으며, 파이썬의 permutations를 활용하여 순열을 구하는 것은 기본적인 알고리즘 자체를 공부하는 것에는 별 도움이 될 것 같지 않아 그냥 직접 구현하는 것을 계속 연습하였다.

처음 코드만 봤을 때, 한눈에 알고리즘의 로직을 이해하는 것은 재귀적 호출이 있어 쉽지 않았으며, 이를 한줄 한줄 뜯어보며 조금이나마 이해를 할 수 있게 됐다.

상세 설명은 주석으로 대신합니다!!!

댓글남기기

참고