[BOJ][Python][15649] N과 M(1)

[문제 및 출처]

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

[어떻게 풀까?]

이 문제는 백트래킹 문제라고 한다. 사실 나는 백트래킹이고 뭐고 다 재귀 같다. 내가 초보자라서 그런지는 몰라도 비슷비슷한 것 같다. 그래서 카테고리도 그냥 재귀에 넣었다. 아무튼

이 문제를 풀다 열심히 고민을 하다 잘 풀리지 않아서, 여러 유튜브와 블로그들을 찾아보았다.

많이 사람들이 Bool형 배열을 이용하여 이를 푸는 것을 보았다. 변수의 이름은 마치 동사처럼 사용하는 것도 보았는데 이것을 사용하면 

코드를 좀 더 현실세계의 언어와 비슷하게 짤 수 있었다.

사실 나도 이 문제가 너무 어렵고 감이 안 잡혀서 코드를 보고 이해하고 다시 생각했다. 

이 글을 보는 당신도 잘 이해가 되지 않는다면 일단 코드를 보고 분석해 보길 바란다.

[코드]

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

used = [False] * (N+1)
answer = []

def dfs(N, M):
    #조건에 충족하면 출력
    if len(answer) == M: 
        print(" ".join(map(str, answer)))
        return

    for i in range(1, N+1):
        if not used[i]: 
            used[i] = True
            answer.append(i)

            dfs(N, M)
            
            #다시초기화
            used[i] = False 
            answer.pop()

dfs(N, M)

[코드 설명] 

백트래킹은 재귀함수와 마찬가지로 함수를 이용해서 문제를 효과적으로 해결한다. 일단 처음에는 N번 반복해 준다. N번 반복하는 과정에서는 또 다시 dfs함수를 호출 해 준다. 이 과정에서 나는 사용된 값에 표시를 해 두었기 때문에 사용된 값은 재사용되지 않는다. 이 과정을 진행하다가 조건을 충족시키면 출력을 해준다. 그러곤 다시 #다시 초기화 부분을 진행해서 마지막 값을 없앤 다음에 반복문을 진행한다. 그렇게 해서 다시 상위 반복문으로 또 다시 상위 반복문으로 가게 된다. 

 

사실 그림으로 이해하면 정말 편하겠지만 내가 아이패드나 기타 그림을 그릴만한 수단은 부족해서 그림은 못그리겠다. 여러분은 머릿속으로 그리든 인터넷으로 찾아보든 알아서 하시길 바라겠다.