백트래킹 문제들이다...
이해하는데 정말 좀 복잡했다.
재귀함수 문제들도 풀이를 할 때, 사실 재귀가 어떻게 돌아가는지를 자세하게 이해하고 풀지는 않고, 뭔가 머릿속에 탁 하고 떠오르는 그 느낌을 구체화시켜서 풀었었기에 백트래킹도 처음에 이해하기가 너무 어려웠다.
어떤 아티클을 봐도 그 진행되는 과정이 한눈에 들어오지 않았고, 무슨 느낌인지 처음에는 감이 안잡힌거 같다.
그러다가 Youtube에 짖는개님의 백트래킹 영상을 보고 머릿속에 구체화가 조금 된 듯 해서 구현하여, 맞았다..
문제는 간단하다.
하지만 항상 간단한 문제가 가장 어렵 듯...
그리고 현실세계에서 쉬운 문제가, 코드로는 구현하기 어렵듯... 어렵다 ㅠ
N과 M 이 주어지면
1 ~ N까지 수 중에서 M개의 숫자를 고르는 문제
그니까 학생 시절 수학을 공부할 때 보면, 모든 케이스를 찾기 위해서 나무 모양의 그림을 그렸던 것을 떠올리면 된다.
그래서 한번 진행해보자
예시
N = 3 , M = 2
1 - 2
1 - 3
2 - 1
2 - 3
3 - 1
3 - 2
이런식으로 중복 되지 않는 2개(M개)의 숫자들을 고르면 되는 것이다.
이걸 구하는 방법이 백트래킹인데, 백트래킹의 간단한 정의를 말하자면 돌아가서 다시 찾아라 라는 것이다
시작
첫번째 숫자가 1이었다면, 그 다음 오는 숫자는 2 (1 - 2)라고 생각할 수 있을 것이고,
그 다음 올 수 있는 케이스는 3이 있기에, 2를 버리고 3을 다시 넣어서 1 - 3이라는 케이스를 생각할 수 있다.
또 첫번째 숫자가 2라면, 그 다음 오는 숫자는 1이라고 생각할 수 있을 것이고,
그 다음 올 수 있는 케이스는 3이 있기에, 1을 빼고 3을 다시 넣어서 2 - 3 이라는 케이스가 온다는 것을 생각할 수 있다.
이제 코드를 보자.
코드로 차근 차근 설명해서 보는 것이 편하더라 오히려
코드
N, M = map(int, input().split(" ")) # N과 M의 입력을 받고
arr = [0] * (M) # arr는 M개만큼 초기화 해준다 --> 이 arr는 표현할 수열들을 임시적으로 저장해놓아주는 배열이다
isused = [False] * (N + 1) # issued는 (N+1)개 만큼 False로 초기화 해주는데, 그 이유는 index 자체를 사용했는지, 안했는지 숫자로 인지할 것이기 때문이다. --> 말한거처럼 이 배열은 index의 수를 사용했는지 안했는지 인식해주는 배열로 사용할 것이다.
def func(k): # k라는 인자를 먼저 받는데, 이 k는 쌓아놓을 단계 그니까 1 - 2 - 3 이런식으로 숫자들의 처음 자리, 두번째 자리 ... 이런식으로 인지되는 인자이다.
if k == M:
for i in range(M):
print(arr[i], end=' ')
print("")
return
for i in range(1, N+1):
if not isused[i]:
arr[k] = i
isused[i] = True
func(k+1)
isused[i] = False
func(0)위의 코드의 써놓은 주석말고 나머지 설명을 차근차근 보자.
설명 순서는 위의 코드와 순서가 다를 수 있다.
for i in range(1, N+1):
if not isused[i]: 1부터 N까지 숫자들을 순회시켜 주면서, 숫자가 쓰였는지 안쓰였는지를 판단하여, 조건문을 실행한다. 조건문 내부를 보자.
arr[k] = i
isused[i] = True
func(k+1)
isused[i] = Falsearr[k] = i 는 해당 단계(k)에서 숫자가 쓰이지 않았다면, 배정해주는 역할을 한다.
isused[i] = True 해당 숫자(i)가 쓰였으니까, 숫자가 쓰였다는 것을 인지시켜준다(해당 인덱스를 True로)
func(k+1) 그 다음 단계로 넘어가서, 위의 과정을 반복한다.
if k == M: #
for i in range(M):
print(arr[i], end=' ')
print("")
return
k == M 그니까 단계가 끝까지 도달하면, 우리가 출력할 단계까지 오면, 모아놓았던 arr의 숫자들을 출력해준다.
이제 코드의 진행을 보자, 나는 처음에 도저히 이해가 안가서 코드 진행 도중 k와 arr와 isused를 다 출력해서 진행을 보았다. 이해가 안가면 다 출력해서 디버깅 한다고 생각하자
func(0) 을 통해서 출력을 진행하기 시작해준다.
k에 0을 주는 이유는 arr가 시작이 0인 0-indexed 배열이기에 0으로 줘야한다.
1단계라고 해서 1을 주는 일이 없도록 주의하자
이해하기 쉽게 인자에 넣은 값을 이용해서 함수를 다시 작성해보면
Ex) N = 3, M = 2
func(0)
if 0 == 2:
for i in range(M):
print(arr[i], end=' ')
print("")
return
###################### 이리로 Jump
for i in range(1, 3+1): # isused = [False, False, False, False]
if not isused[i]: # i = 1 부터, isused가 False이므로 => 사용되지 않았다고 인식
arr[k] = i # 0단계 = 1
isused[i] = True # isused = [False, True, False, False] --> 1은 사용되었다고 표시
func(1) # 다시 func에 1을 넘겨주므로써, 0단계 숫자는 이미 골랐고, 그 다음 단계 숫자를 고르라고 명시 다시 위의 코드 진행
isused[i] = False # func함수가 끝나는 시점은 단계의 끝인 M이 되었을 때니까 func함수가 끝나면, 재귀함수를 하나하나 탈출할 때마다, 그 수의 사용을 마쳤다고 인지시켜준다.디버깅 하기 위해 k, arr, isused 를 단계마다 출력시켜 본 결과를 확인해 보면
3 2
k : 0
arr : [0, 0]
isused : [False, False, False, False]
=====================================
k : 1
arr : [1, 0]
isused : [False, True, False, False]
=====================================
k : 2
arr : [1, 2]
isused : [False, True, True, False]
=====================================
***********************
1 2
***********************
k = 2 가 되었을 때 출력해주고, 그 다음으로 넘어가는 코드를 보면
isused[2]를 False로 바꾸어, 사용하지 않았다고 표지해주고
그다음 수인 3으로 넘어가는 것을 볼 수 있다.
k : 2
arr : [1, 3]
isused : [False, True, False, True]
=====================================
***********************
1 3
***********************
3일 때도 똑같이 진행해주고
끝까지 돌았기에, 재귀로 들어간 func을 탈출해준다.
k : 1
arr : [2, 3]
isused : [False, False, True, False]
=====================================
k : 2
얘는 반복문에서 그니까 func를 탈출하고, 처음 func에서 i가 2로 넘어간 시점이라고 생각할 수 있다.
arr : [2, 1]
isused : [False, True, True, False]
=====================================
***********************
2 1
***********************
k : 2
arr : [2, 3]
isused : [False, False, True, True]
=====================================
***********************
2 3
***********************
k : 1
arr : [3, 3]
isused : [False, False, False, True]
=====================================
k : 2
arr : [3, 1]
isused : [False, True, False, True]
=====================================
***********************
3 1
***********************
k : 2
arr : [3, 2]
isused : [False, False, True, True]
=====================================
***********************
3 2
***********************이런식으로 이해할 수 있다.
boj-15650(N과 M (2))
그다음 boj-15650 문제는 이 배열을 표시하되, 오름차순으로만 되어있는 수를 표시하는 문제였다.
살짝 고민해보고, 바로 해결하였다.
def func(k, t):
if k == M:
for i in range(M):
print(arr[i], end=' ')
print("")
return
for i in range(t, N+1):
if not isused[i]:
arr[k] = i
isused[i] = True
func(k+1, i)
isused[i] = False
N, M = map(int, input().split(" "))
arr = [0] * (M)
isused = [False] * (N + 1)
func(0, 1)func 함수에 t라는 인자를 새롭게 넘겨주는데, 이 t는 진행되던 i까지의 숫자를 넘겨주는 것이다.
그리고 for i in range(t, N+1):으로t부터 검사
즉, 진행되던 i이후로 숫자부터 반복하여 진행하라는 것.
boj-15651(N과 M (3))
boj-15651은 15649랑 똑같지만, 중복을 허용해서 표현해준다.
이건 진짜 간단한데, 중복을 허용하지 않기 위해 만들어놓았던 isused를 사용하지 않으면 된다.
def func(k):
if k == M:
for i in range(M):
print(arr[i], end=' ')
print("")
return
for i in range(1, N+1):
arr[k] = i
func(k+1)
N, M = map(int, input().split(" "))
arr = [0] * (M)
func(0)isused 의 역할은 사용되었던 수를 다시 사용하지 않기 위함이었다.
그렇기에 isused가 사용된 부분들을 삭제해주면, 중복되어 출력할 수 있다.
boj-15652(N과 M (4))
(2) 과 (3)의 짬뽕이기에 자세한 설명은 생략한다.
def func(k, t):
if k == M:
for i in range(M):
print(arr[i], end=' ')
print("")
return
for i in range(t, N+1):
arr[k] = i
func(k+1, i)
N, M = map(int, input().split(" "))
arr = [0] * (M)
func(0, 1)
