파이썬 내장함수인 조합을 쓰면 되겠다고 바로 떠올렸다. 문제는 출력 방법! permutations의 형식을 잘 알지 못해 출력해가며 올바른 정답 코드를 찾았다. 그런데 이 문제는 백트래킹에 분류되어 있다! 백트래킹으로 다시 문제를 풀어보았다.
조합을 이용한 코드
import sys, itertools
input = sys.stdin.readline
N, M = map(int, input().split())
lst = [i+1 for i in range(N)]
nPr = itertools.permutations(lst, M)
for i in nPr:
print(*i)-
print(nPr)하면 <itertools.permutations object at 0x105574040>가 뜨면서 itertools.permutations 객체를 직접 출력한다.
-
그치만 이는 반복가능한 객체이기에 굳이 list로 바꾸지 않고 for문으로 개별 원소에 접근할 수 있다.
-
반복가능한 객체라 print(*nPr)도 당연히 가능하다. 이를 이용해서 nPr을 출력해보면 아래와 같다.
- 입력이 3 1일 때
(1,) (2,) (3,) - 입력이 4 2일 때
(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)
- 입력이 3 1일 때
-
이제 문제 의도에 맞게 1 2 형식으로 출력해보자. 즉, 튜플의 개별 원소를 공백으로 구분해서 출력하면 되므로 *연산자를 사용해서 튜플의 모든 원소를 개별 값으로 풀어 출력하자.
-
이를 모두 합치면 아래와 같다.
for i in nPr:
print(*i)백트래킹
- 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다가 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 올라가는(방금 왔던 길을 되짚어가는) 알고리즘이다.
백트래킹 vs DFS
- 백트래킹: 불필요한 탐색은 하지 않음
- DFS: 모든 경우의 수를 탐색
즉, 백트래킹은 모든 경우의 수를 탐색하는 대신, 조건을 걸어서 유망(promising)하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서 다른 경우를 탐색한다.
코드
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
lst = []
def backtracking():
if len(lst) == M:
print(*lst)
return
for i in range(1, N+1):
if i not in lst:
lst.append(i)
backtracking()
lst.pop()
backtracking()- 도저히 내 머릿속으론 재귀를 찾을 수가 없어서.. 다른 코드들을 참고했다.
풀이
- 내가 이해한 바로는, backtracking()하는 게 가지치기를 하는 거고 pop()하는 게 거슬러 올라가서 다음 단계로 넘어가는 거라고 생각했다.
- 예를 들어 N=4, M=3인 경우를 생각해보자.
i=1일 때 lst에 넣고, 재귀에 들어가서 다시 for문을 i=1부터 돈다.
1은 리스트에 있으니까 2를 넣고, 또 다시 backtracking을 호출. 그러면 아래 그림처럼 가지를 뻗고 2가 그려진다.
그럼 이제 3번째 for문을 도는데 1, 2는 리스트에 있으므로 3을 넣는다. 또 bracktracking을 호출하고 3 노드가 그려진다.
이번에는 lst의 길이가 M이다. 그러므로 1 2 3을 출력. 그럼 3번째 for문(이때 i=3)에서 backtracking의 호출이 끝났으므로 pop을 시행한다. 그러면 3이 pop되고 다음 i=4가 수행된다.
즉, pop()하는 것이 아래 과정에서 3 다음 4로 가기 위해 거슬러 올라가는 과정(보라색 화살표)으로 나는 이해했다.
결과
- 위에가 백트래킹을 이용한 코드이다.
- 백트래킹 어렵군!
