백준 15649번
이번 문제는 백트래킹 문제인데, 알고리즘 고자인 나는…. 그냥 해답을 찾고 이해할 수 밖에 없었다ㅠ 흑흑
우선 백트래킹이 뭔지도 몰랐고..
DFS를 기본으로 로직을 구성해나가야하는데 DFS, BFS 공부도 제대로 해본적이 없어서 그냥 해답을 보고 이해했당 ㅠ 그래도 좋은 레퍼런스가 많아서 공부가 많이된 것 같아 감사하다!
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
우선 아무것도 고르지 않았을 때, N가지의 자연수를 고를 수 있다.
아무것도 고르지 않은 상태를 False 상태로 두자
M번의 자연수를 골랐을 때 하나의 경우가 완성되는데, M번까지 세어주는 변수를 만들자.
그리고 하나의 경우의 수가 완성 될때까지 값을 담아두는 리스트를 만들자.
경우의 수를 만들어주는 함수를 만들자.
N, M = map(int, input().split())
v = [False] * N
nlist = []
def recursive(cnt, N, M):
if cnt == M:
print(' '.join(map(str, nlist)))
return
for i in range(N):
if not v[i]:
nlist.append(i+1)
v[i] = True
recursive(cnt+1, N, M)
v[i] = False
nlist.pop()
recursive(0, N, M)
재귀함수를 만들었을 때 많이 헷갈렸는데, 어떻게 함수에 3가지 변수를 받아서 확인해볼 생각을 할까?
진짜 알고리즘 어렵다…
재귀함수를 도는데, N가지의 자연수를 고를 수 있고, M번 뽑을 수 있다. 그리고 몇 번 뽑았는지 세어주는 cnt를 받는다.
재귀함수가 실행되면, 우선 **몇 번 뽑았는지**(cnt)를 체크한다. M번 뽑았으면 print하고 함수를 끝낸다.
M번 뽑지 않았으면 if문을 통과하고 for문으로 내려온다. for문은 1~N까지 자연수를 고르도록 하는데, 이미 뽑은 자연수인지 v리스트로 체크한다.
v리스트의 i번째가 False이면, 아직 뽑히지 않은 자연수 이므로 **뽑아주기를 해주고**`v[i] = True`
뽑힌 자연수를 담는 nlist에 추가해준다. `nlist.append(i+1)` 여기서 i+1을 해주는 이유는 range 함수가 0부터 시작하는데에 반해 문제 조건은 1부터 N까지인 자연수이기 때문이다. `range(1, N+1)`로 코드를 짜고 `nlist.append(i)`로 짜도 무방하다.
그리고 i를 뽑았으니 이제 cnt+1을 해주고 재귀함수를 다시 돌게 해준다. 그렇게 cnt가 M과 같아지면(M번 뽑았으면) print하고 함수가 끝난다.
재귀함수 특성상 해당 함수 내 마지막 줄까지 코드가 읽히는게 아니면 함수가 끝나지 않는다. recursive(recusive(recursive(....))) 이런식으로 함수 스택이 쌓이기 때문에 계속 recursive 함수가 새로 만들어지다가 cnt와 M이 같아지는 시점, 즉 **M번 모두 뽑은 경우**에 print함수가 실행되고 **return**이 나옴으로써 제일 안쪽에서 실행된 함수가 끝나게된다.
그리고 다음줄이 실행되는데 그 다음줄엔 해당 경우의 수가 다 끝나서 출력까지 완료한 상태이므로, v리스트의 i번째를 다시 False로 만들어준다. 그리고 nlist에 담았던 **뽑았던 수**를 pop해준다. 그리고 해당 recursive 함수가 끝난다.
**여기가 헷갈린당**
제일 안쪽에 있던 recursive 함수의 cnt값이 M과 같은데, 해당 함수는 종료되었고 그 밖에 있는 함수는 마지막에 뽑혀서 nlist에 추가된 값이 pop되었는데, **중요한 점! for문은 살아있다.**
그 다음 i 값이 들어가서 v리스트의 i번째가 False인지 확인(뽑힌 수인지 확인!)하고 False이면 또 nlist에 담는다. 담고 v[i]를 True로 바꿔주고 recursive를 또 `cnt+1`해서 실행한다.
그러면 또 cnt+1은 M과 같아지므로 print하고 종료된다. 그리고 또 다시 바깥의 같은 함수로 나와서 for문이 끝날때까지 돌고 마지막으로 뽑힌 수를 빼고 종료된다.
그리고 그 밖에 있는 cnt는 M과 값이 2가 차이가 날 것이다. 그리고 남은 for문을 돌아 i를 바꾸고, recursive 함수를 실행해서 그 안에서는 cnt+1 값이 들어가 같은 행위를 반복한다.
그리고 그 밖에 자기 함수 안에있던 recursice 함수가 종료된 후 자신의 v리스트 i를 또 False로 만들고, 해당 뽑았던 수를 또 내보낸다. 그렇게 recursive 함수가 끝나면 뽑은 수를 담는 리스트는 비워지고, v리스트 내부도 다시 처음 상태인 False로 모두 바뀐다.
내가 이해하면서 바로 써내려간 글인데, 내가 봐도 다시 안읽을듯….어쩔거야~~~ㅜㅜㅜ
사실 아래 코드를 다시 짜본것이다 ㅠ
코드는 완전 똑같지만… 내가 이해해보려고 변수를 다르게 직접 짜서 풀었다.
N, M = map(int, input().split())
visited = [False] * N # 탐사 여부 check
out = [] # 출력 내용
def solve(depth, N, M):
if depth == M: # 탈출 조건
print(' '.join(map(str, out))) # list를 str으로 합쳐 출력
return
for i in range(len(visited)): # 탐사 check 하면서
if not visited[i]: # 탐사 안했다면
visited[i] = True # 탐사 시작(중복 제거)
out.append(i+1) # 탐사 내용
solve(depth+1, N, M) # 깊이 우선 탐색
visited[i] = False # 깊이 탐사 완료
out.pop() # 탐사 내용 제거
solve(0, N, M)
백트래킹의 개념도 되짚어보자.
백트래킹
백트래킹의 가장 요점은 가능성이 없다고 판단되는 즉시 해당 경우를 포기하여 정답을 찾아가는 알고리즘으로 제약충족 문제를 풀 때 사용된다고 한다.
#### 제약충족 문제란?
방탈출 같은 게임을 예로 들 수 있다. 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 경우의 수를 따라 들어가며 탐색하는 알고리즘을 말한다.
기본적으로 재귀함수가 꼭 들어가게 될 것이고, A를 고르면 그 다음 A를 고른 후의 상황을 탐색하는 경우의 제약 상황을 고려한다.