[BaekJoon] 백준 15649번 N과 M(1)

[BaekJoon] 백준 15649번 N과 M(1)

 

문제: www.acmicpc.net/problem/15649

 

내코드

 

• 백트래킹 문제: 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
• 백트래킹 문제를 처음 풀어보는 것이기도 했고, 구현 과정이 상당히 어려웠다.
• 리스트에 값을 하나씩 넣어주면서 풀어주는 문제
• 만약 1-4의 수가 있고, 2자리 수열을 만들어줘야 한다고 가정해보자.
  • [1, x] -> [1, 2] -> [1, 3] -> [1, 4] -> [2, x] -> [2, 1] -> [2, 3] -> [2, 4]
  • 이런식으로 리스트에 수가 들어갈것
  • 수가 사용될때마다 visited에서 해당 값은 True로 처리

 

n, m = map(int, input().split())
visited = [False] * n  # 사용 여부 확인용
out = []  # 출력 내용

def solve(depth, N, M):
    if depth == M:  # 길이가 m인 리스트가 완성되었다면
        print(' '.join(map(str, out)))  # 출력
        return
    for i in range(n): # 1-n까지 수를 돌아가며
        if not visited[i]:  # i 값 사용을 아직 하지 않았다면
            visited[i] = True  # i 사용 여부 true
            out.append(i+1)  # 사용한 것 리스트에 기록
            solve(depth+1, N, M)  # 리스트의 다음 수 정하러 들어감
            visited[i] = False  # k번째 수를 i로 정한 경우를 모두 확인했으므로 i를 이제 사용x
            out.pop()  # k번째 수를 i로 정한 경우를 모두 확인했으므로 k번째 수를 pop하기(다음 수를 k번째에 집어넣기 위해)

solve(0, n, m)

 

참고

blog.encrypted.gg/732?category=773649

wlstyql.tistory.com/56