15664번: N과 M(10)

15664번: N과 M (10)

 

N과M 10번째 문제다.

이전에 풀었던 문제와 거의 비슷하다.

 

---

# 15664번: N과 M (10)

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [False] * n

result = []


def backTracking(num):
    if len(result) == m:
        print(*result)
        return
    
    remember = 0

    for i in range(num, n):
        if not visited[i] and arr[i] != remember:
            visited[i] = True
            result.append(arr[i])
            remember = arr[i]
            backTracking(i + 1)
            visited[i] = False
            result.pop()


backTracking(0)

 

이 코드를 작성하기까지 어떻게 생각했는지 기록하려고 한다.

 

먼저, N개 중 M개를 골라야하는데, 비내림차순으로 골라야한다.

그리고 같은 원소를 중복해서 고르면 안된다.

 

일단 비내림차순으로 원소를 골라야하므로, backTracking함수에서 다음 backTracking으로 넘어갈 때,

그 다음으로 위치한 원소를 골라야하므로, 해당 정보를 인자로 넣어줘야겠다는 생각을 했다.

만약 for문 안에서 i번째 원소를 넣어줬을 경우에는 그 다음에는 i+1번째 원소부터 들어갈 수 있는 후보가 된다.

그러므로 backTracking(i+1)이런식으로 재귀식을 넣어줘야 한다.

 

처음에는 backTracking(num + 1)로 넣어줬다가 나중에 더 방금 전에 넣었던 수보다 더 작은수도 들어가버리는 문제가 발생했다.

 

그리고 무엇보다 remember 변수를 왜 쓰는지 이해하는 게 중요하다.

remember 변수는 방금 전에 넣은 수의 값을 기록하는 변수다.

이 변수를 통해 중복을 걸러준다고 할 수 있다.

 

예를 들어 입력값이

4 2

9 7 9 1

이라고 생각해보자.

4개 중 2개를 뽑는 것이고, 중복되는 수열을 뽑으면 안된다.

9 7 9 1을 오름차순 정렬을 통해 1 7 9 9로 만들어준다.

 

그리고 백트래킹을 돌면서

1 7

1(1) 9(2)

를 출력했을 때의 상황을 생각해보자. (괄호 안의 값은 인덱스)

1 9 를 출력하고 return을 통해 해당 backTracking함수를 빠져나온다.

visited[i] = False를 통해 visited[2] = False로 만들어준다.

그리고 result.pop()을 통해 result리스트는 [1(1)]이 된다.

이 때의 remember 변수의 값은 9이다.

 

그리고 다음 인덱스인 3번째 인덱스의 수 9(3)를 확인한다고 해보자.

visited[3] = False이므로 다음 조건으로 넘어간다.

arr[3] = 9이고, remeber = 9이므로 해당 수는 result 리스트에 들어갈 수가 없다.

arr[i] != remember 이 조건에서 중복수열을 걸러줄 수 있는 것이다.

만약 중복수열이 되려는 순간, 그 수는 바로 넘어가버린다, 즉 가지치기를 해버린다.

 

이 이후에도 

7(1) 9(2)

다음에

7(1) 9(3)도 가지치기 되버린다.

 

이런 방식으로 가지치기를 통해 효과적으로 DFS를 도는 것이 백트래킹의 핵심이라고 할 수 있다.