💡 백준 6603:
DFS 탐색을 통해 가능한 모든 조합의 경우 확인
🌱 코드 in Python
알고리즘: BFS & DFS
import sys
input = sys.stdin.readline
def dfs(dep, i):
if dep == 6:
print(*ret)
return
for i in range(i, k):
if dep + k - i < 6: # 정답 배열에 넣으려는 인덱스를 더했을 경우 남은 요소들을 다 채워도 최종 길이를 만족하지 못한다면
return 해당 재귀문 종료
ret.append(s[i]) # 최종 길이를 만족할 수 있을 경우만 append
dfs(dep + 1, i + 1) # 재귀
ret.pop() # 다음 요소 탐색을 위해 pop
while True:
g = list(map(int, input().split()))
k = g[0]
s = g[1:]
if k == 0:
break
ret = []
dfs(0, 0)
print()이번 문제는 주어진 길이의 숫자 배열에서 6가지를 고르는 모든 조합의 경우를 탐색하는 문제였다
요 며칠 브루트포스 문제를 통해 조합문제를 풀었는데, 그때마다 combinations 모듈을 사용하여 풀었다
하지만 라이브러리 없이 조합 문제를 푸는 방법을 알아두는 것이 좋을 것 같아 이번 문제를 풀어보게 되었다
dfs 재귀문으로 돌렸으며
for i in range(i, k):
if dep + k - i < 6:
return 해당 재귀문 종료
ret.append(s[i])
dfs(dep + 1, i + 1)
ret.pop()이부분이 핵심이라고 볼 수 있을 것 같다
for문 i는 만약 숫자 배열이 1 ~ 7까지 있다고 할 때 숫자를 골라주는 역할을 한다
1, 2, 3, 4, 5, 6 , 2, 3, 4, 5, 6, 7처럼 말이다
이후 dep와 i를 같이 증가하여 또 다시 dfs를 돌리면
1, 2, 3, 4, 5, 6 -> 1, 2, 3, 4, 5, 7로 마지막 요소 6을 pop하고
5번의 재귀문이 이전에 6까지 돌았으니 7 for문을 또 돌려서 다른 조합을 만들어 낼 수 있게 된다
if dep + k - i < 6:
return 해당 재귀문 종료이 부분은 사실 없어도 무방한 코드인데 의미없는 재귀를 피하기 위해 추가하였다
만약 1, 2, 3까지 채워져있는 배열에서 다음 4번째 인덱스 값에 5에 해당하는 for문과 재귀문까지 끝나고
1, 2, 3, 6를 채워 재귀문을 탐색한다고 가정하자
1, 2, 3, 6, 7, 1, 2, 3, 7과 같은 배열들이 만들어졌을 것이다
그러나 이때 두 배열모두 원하는 길이인 6을 만족하지 못한다
따라서 1, 2, 3, 6을 검증할 때 사용할 수 있는 숫자의 갯수는 7 하나로 6을 추가해봐야 남은 숫자들로 6을 만들지 못한다
이런 때 불필요한 재귀문이 발생하므로 이를 방지할 수 있는 것이 바로 위 조건문이다
재귀문에 대한 소요를 줄이고 배열에 append - pop 하는 과정을 줄여 시간을 줄여보려 한 것인데,
결론적으로 백준 기준 시간은 별로 줄지 않았다 ㅎ
약간 뻘짓한 것 같지만, 그래도 재귀문을 많이 돌지 않는 것은 만족스럽다
요거 잘 기억해뒀다 나중에 조합문제 풀게 되면 또 잘 풀어야징 ㅎㅎ
🧠 기억하자
-
조합을 라이브러리 없이 풀자!
-
로또 당첨 되면 얼마나 좋을까!
