• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

조합 구하는 DFS 질문

23.09.23 00:01 작성 23.09.23 00:03 수정 조회수 138

0

numbers = [2, 1, 3, 4, 1]
def dfs(L, s):
    global tmp
    if L == 2:
        num_list.append(tmp)
        tmp = list()
        return
    else:
        for i in range(s, len(numbers)):
            tmp.append(i)
            dfs(L+1, i+1)

tmp = list()
num_list = list()
dfs(0, 0)
print(num_list)

인덱스를 [[0, 1], [0,2], [0,3], [0,4], [1, 2], [1,3], [1,4], [2, 3], [2,4], [3, 4]] 뽑고 싶은데

[[0, 1], [2], [3], [4], [1, 2], [3], [4], [2, 3], [4], [3, 4]] 이렇게 나옵니다.

6번 라인 tmp = list() > tmp.pop() 으로 수정하면 될 것 같은데 결과값은 안나오네요.

어떤 부분을 실수했는지 감은 오는데 코드로 구현하는 법은 모르겠네요.

도움부탁드립니다.

 

답변 1

답변을 작성해보세요.

0

안녕하세요^^

아래처럼 코드를 하시면 됩니다. 특히 tmp[:]와 같이 슬라이싱으로 깊을 복사를 해야 합니다.

numbers = [2, 1, 3, 4, 1]
def dfs(L, s):
    global tmp
    if L == 2:
        num_list.append(tmp[:])
        return
    else:
        for i in range(s, len(numbers)):
            tmp.append(i)
            dfs(L+1, i+1)
            tmp.pop()

tmp = list()
num_list = list()
dfs(0, 0)
print(num_list)