[알고리즘] 백준 DFS 문제를 풀며 저질렀던 실수들..

백준 15663번 문제를 2시간 넘게 풀며.. 생각보다 간단한 문젠데 왜 안풀릴까.. 하고 고통을 받았다. 결국 인터넷을 통해 답을 찾게 되었는데, 나의 접근과 크게 다르지 않아 (사실 문제가 그렇게 어렵지 않았음) 뭐가 문제였을까? 하고 스스로의 문제풀이를 다시 돌아봤는데, 알고리즘 문제를 푸는 사람으로써 치명적인 실수들을 하고 있음을 알게되어 이를 정리하여 앞으로의 문제 풀이에서는 같은 실수를 반복하지 않도록 하려합니다.

제가 알고리즘 문제 풀이 시에 간과했던 부분은 재귀 함수에서 변수와 관련된 부분이었습니다.

문제

나의 풀이

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
nums = list(map(int,sys.stdin.readline().split()))
nums = sorted(nums)

collected = []
visited = [False] * n

def DFS(l):
    #global l
    if len(l) == m:
        if l in collected:
            pass
        else:
            collected.append(l)

    else:
        for i in range(n):
            if visited[i] == False:
                l.append(nums[i])
                visited[i] = True
                DFS(l)
                l = l[:-1]
                visited[i] = False
                
l=[]
DFS(l)
for i in collected:
    print(*i)

이렇게 문제를 풀었는데, 나름 조건도 다 주고, DFS를 통해서 백트랙킹을 잘 풀었다고 생각했다.
그러나 결과는...

n=4, m=2, nums = [9,7,9,1]
>>> 1 7
>>> 1 9

결과를 보니 l의 0번째 자리에 1이 아닌 다른 수가 오지 못하고 [1 7][1 9] 만 반복해서 들어가고 있었다.

오답 노트

이 문제를 해결하기 위해 찾아보니 내가 2가지의 잘못을 저지르고 있었다.

1. collected.append(l) -> collected.append(l[:])

   • 정답들을 보관할 리스트인 collected에 정답들(l)을 append 하는 과정에서 l을 그대로 받다보니 추후에 l이 변경될 경우에 collected에 저장된 l도 같이 변하는 것을 알 수 있었다. 이 문제를 해결하기 위해서는 l[:]을 통해 원소들의 값만 복제해서 append 해야 l의 변화에 영향을 받지 않도록 하자!!

2. l=l[:-1] -> l.pop()

   • DFS 함수의 인자로 l이 들어가게 된다. DFS는 재귀함수이기 때문에 인자의 변화에 민감하게 반응할 수 밖에 없는데, l=l[:-1]의 기능은 l.pop()과 동일할 수 있지만 같은 l이 아닌 l이 새롭게 정의되는 것이기 때문에 같은 변수의 이름이라고 하더라도 다른 값으로 처리될 수 있다. 이 때 l.pop()은 값을 새로 정의하지 않으면서 마지막 인자를 제거해주기 때문에 l=l[:-1]보다 효율적이면서도 혼동이 없어 재귀함수에서 훨씬 용이하다.
     앞으로는 pop(),append() 등 스택 함수들을 활용해야겠다.

수정 코드

물론 시간초과가 뜨긴 했지만 저 스스로 있었던 오류를 해결한 풀이는 아래와 같습니다. 시간초과를 해결하기 위해서는 첫번째 if문의 조건을 두번째 else의 for 문의 조건으로 추가하면 됩니다. 아래 참고하시면 정답을 얻을 수 있습니다.

정답 블로그

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
nums = list(map(int,sys.stdin.readline().split()))
nums = sorted(nums)

collected = []
visited = [False] * n

def DFS(l):
    if len(l) == m:
        if l in collected:
            pass
        else:
            collected.append(l[:])

    else:
        for i in range(n):
            if visited[i] == False:
                l.append(nums[i])
                visited[i] = True
                DFS(l)
                l.pop()
                visited[i] = False
                
l=[]
DFS(l)
for i in collected:
    print(*i)

결론

오늘은 알고리즘 재귀 문제를 풀 때 저지를 수 있는 실수들에 대해 알아보았습니다. 재귀 함수의 개념을 잘 활용하면서도 이러한 사소한 부분을 놓치지 않도록 주의해야겠습니다.