15649번: N과 M(1)

15649번: N과 M (1)

 

 

백트래킹 문제다.

 

---

이 문제는 2가지 방식으로 풀 수 있다.

 

# 15649번: N과 M(1)

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

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

def backTracking(num):
    if num == m:
        print(" ".join(map(str, result)))
        return
    
    for i in range(1, n+1):
        if not visited[i]:
            visited[i] = True
            result.append(i)
            backTracking(num + 1)
            visited[i] = False
            result.pop()


def backTracking2(num):
    if num == m:
        print(" ".join(map(str, result)))
        return
    
    for i in range(1, n+1):
        if i not in result:
            result.append(i)
            backTracking2(num + 1)
            result.pop()


# backTracking(0)
backTracking2(0)

 

이런 식으로 푼다.

핵심은 특정 원소를 방문한 후, 재귀를 나오면서 다시 방문 안한 것처럼 처리해주는 것이다.

백트래킹 문제 대부분이 이런 로직을 사용한다.

문제를 풀다가 모르겠으면, 직접 로직을 그려보며, 재귀함수를 구현하자.