[Python] 15650번 N과 M (2)

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

15650번: N과 M (2)

---

 

22/06/25

 

 

옛날에 풀었던 문제를 오늘(22/12/01) 백트래킹으로 다시 풀어보았다.

 

이전에는 파이썬의 itertools묘듈의 combinations를 사용해서 문제를 해결했지만, 백트래킹을 연습하는 문제로, 백트래킹으로 풀어보기로 했다.

---

 

문제 접근 방식:

 

 

첫 번째 접근 방법은 N과 M (1)의 코드를 변형한 코드이다.

 

2022.12.01 - [백준 문제 풀이] - [Python] 15649번 N과 M (1)

[Python] 15649번 N과 M (1)

 위의 코드를 보면 dfs로 모든 순열을 출력했다.

 

이때 visited 배열을 활용하는데, 이 visited 배열은 중복되는 숫자가 없게끔 출력을 도와주는 역할을 한다.

 

우리가 원하는 것은 순열이 아니라 조합이다.

 

예를 들어, 3개의 숫자에서 1과 2를 출력하는 것이나, 2와 1을 출력하는 것이나 실질적으로 visited 배열에 체크된 모습은 같기 때문에, 우리는 이런 상황을 피해야 한다.

 

따라서, 출력하기 직전의 visited의 상황을 저장해주는 visited_set을 활용하여, 출력할 때 visited 배열의 모습이 지금까지 나오지 않았던 visited 배열의 모습일 때만 출력하도록 바꿔주었다.

 

 

두 번째 접근 방법은 조합의 특성을 활용한 백트래킹이다.

 

예를 들어, 4개의 숫자가 있고 2개를 뽑는다고 해보자.

 

그러면 1 2, 1 3, 1 4까지 탐색하면 이후에는 1을 탐색할 필요가 없다.

 

왜냐하면 1이 들어간 모든 조합들을 전부 탐색했기 때문이다.

 

이후 2를 탐색할 때에는 숫자 2 위에 있는 숫자만 골라서 탐색을 하면 된다.

 

 

이 원리를 이용하여, dfs를 진행할 때 visited 배열을 진행하는 것이 아니라 lower_limit라는 인자를 받아, for문을 돌릴 때 이 lower_limit 이상으로 for문이 돌려지게끔 진행했다.

 

 

두 방법 모두 좋은 방법이니, 잘 익혀두면 많은 도움이 될 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 15650번 N과 M (2)
# 백트래킹
import sys

def dfs(count, num_arr):
    if count == M and tuple(visited) not in visited_set:
        print(*num_arr)
        visited_set.add(tuple(visited))
        return
    for i in range(1, N+1):
        if visited[i] == 0:
            num_arr.append(i)
            visited[i] = 1
            dfs(count+1, num_arr)
            num_arr.pop()
            visited[i] = 0
    

N, M = map(int, input().split())
visited = [0 for _ in range(N+1)]
visited_set = set()
dfs(0, [])

# 15650번 N과 M (2)
# 백트래킹
import sys

def dfs(lower_limit, num_arr):
    if len(num_arr) == M:
        print(*num_arr)
        return
    for i in range(lower_limit, N+1):
        if i not in num_arr:
            num_arr.append(i)
            dfs(i+1, num_arr)
            num_arr.pop()
    

N, M = map(int, input().split())
dfs(1, [])