[BOJ] 15663 : N과 M (9) [백트랙킹](Python)

문제 링크

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

소스 코드

def main():
    n,m = map(int,input().split())
    nums = list(map(int, input().split()))
    visited = [False] * n # 방문 여부
    answers = []

    def permuatation(nums,n,m,arr):
        if len(arr) == m:
            answers.append(arr[:]) # 정답 리스트에 추가
            return

        for i in range(len(nums)):
            if not visited[i]: # 방문하지 않은 경우만
                visited[i] = True # 방문 처리
                arr.append(nums[i])
                permuatation(nums,n,m,arr)
                visited[i] = False # 방문 해제
                arr.pop()

    permuatation(nums,n,m,[])
    answers = sorted(list(set(map(tuple, answers)))) # 중복 제거 및 정렬
    for answer in answers:
        print(*answer,sep=' ')

if __name__ == '__main__':
    main()

 

해설

• 백트랙킹, DFS

시간초과를 어떻게 해결?

사실 논리 자체는 굉장히 간단합니다.

(물론 어렵게 느끼는 분도 있겠지만 n과 m 문제를 여러 개 풀어보셨다면..)

다른 기초 백트랙킹 문제들과 마찬가지로 우리가 새로 만드는 리스트의 길이가 뽑는 개수 m과 동일하면 답으로 저장(또는 출력)하고,

그 길이가 아직 m이 아니라면 주어진 숫자들을 새로 집어 넣는 과정을 반복하는 것이죠.

 

그런데 이 문제는 그렇게 풀이하면 시간 초과 판정을 받습니다.

(저도 아무 생각 없이 풀었다가 ㅜㅜ)

주어진 리스트 안에 같은 숫자가 여러 개 들어 있을수도 있기 때문에 가능한 조합을 다 구하고 여기서 중복을 제거하면 안된다는 뜻입니다.

 

문제 조건에 따르면 n의 최댓값은 8입니다.

그런데 어떤 경우에도 이미 체크했던 곳까지 또 리스트에 추가하고 나중에 중복을 제거하게 되면 얼마나 비효율적일까요?

[1(0), 1(1), 2, 3] 리스트에서 두 개를 뽑는 것으로 예시를 들어봅니다.

여기서 괄호 안의 값은 두 숫자를 구분하기 위해 인덱스를 표시한 것입니다.

 

방문 여부와 상관없이 조합을 구성하면 다음과 같습니다.

[1(0), 1(0)], [1(0), 1(1)], [1(0), 2], [1(0), 3], [1(1), 1(0)], [1(1), 1(1)] ...

 

결국 [1, 1]은 한 번만 출력되어야 하는데 여러 번 중복되는 것을 볼 수 있습니다.

이를 해결하기 위해 방문 처리를 담당하는 리스트를 만들 수 있습니다.

즉, 리스트 내의 각 숫자를 방문할 때 이를 인덱스에 따라 방문했는지 그렇지 않은지를 기록하여 중복되는 방문을 하지 않도록 유도하는 것이죠.

for i in range(len(nums)):
    if not visited[i]: # 방문하지 않은 경우만
        visited[i] = True # 방문 처리
        arr.append(nums[i])
        permuatation(nums,n,m,arr)
        visited[i] = False # 방문 해제
        arr.pop()

물론 백트랙킹의 로직에 따라 재귀함수가 return된 이후에는 다른 값으로 탐색을 진행할 수 있도록 pop과 함께 다시 False로 돌려 놓아야 합니다.

visited를 통해 방문 처리를 하는 것은 하나의 리스트를 구성할 때 이미 방문했던 곳을 또 가서 추가하는 것을 방지하기 위함이니까요!