중복 제거 조건 질문

Introduction to Python Algorithm Problem Solving (Coding Test Preparation)

8. Finding Permutations (DFS)

Written on

205

제가 처음에 중복제거 조건을 flag를 이용한게 아니라 아래와 같이 res에 없는 원소이면 넣는거로 중복제거를 하려고 접근을 했습니다.

답이 [3,1], [3,2]는 들어가지 않았는데 혹시 이렇게 접근하면 왜 안되는건지 설명 부탁드릴 수 있을까요? 잘 이해가 안가서요 ㅠㅠ

감사합니다!

n = 3
m = 2
res = [0 for i in range(m)]
cnt = 0
def DFS(index):
    global cnt
    if index == m:
        print(res)
        cnt+=1
        return
    else:
        for i in range(n):
            if i+1 not in res:
                res[index] = i+1
                DFS(index+1)
DFS(0)
print(cnt)

--------
[1, 2]
[1, 3]
[2, 1]
[2, 3]
4

python코테 준비 같이 해요!

Answer 2

wooli60499

Questioner

아 그렇겠네요! 이해했습니다 감사합니다!

codingcamp

Instructor

[2, 3]에서 index값만 작아지면서 2값이 있는 자리에 3을 넣으려고 하면 이미 res에 3이 있기 때문에 if i+1 not in res 가 참이 되지 않아 [3, 2]로 진행되지 않는 것입니다. 이런 방법으로 할 때는 index가 작아질 때 res의 값도 지우고 작아져야 합니다.

아래 코드처럼 하면 답이 나옵니다.

n = 3
m = 2
res = [0 for i in range(m)]
cnt = 0
def DFS(index):
    global cnt
    if index == m:
        print(res)
        cnt+=1
    else:
        for i in range(n):
            if i+1 not in res:
                res[index] = i+1
                DFS(index+1)
                res[index]=0
DFS(0)
print(cnt)

Inflearn Community Q&A

중복 제거 조건 질문