[백준] 15649 N과 M (Python 파이썬)

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

15649번: N과 M (1)

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

---

풀이 과정

1부터 n까지의 수 중, 중복없이 m개의 수를 나열하는 문제이다.

즉, 1부터 n까지의 수 중 m개의 수를 나열하는 중복을 허락하지 않는 순열이다.

 

예를 들어, n = 4, m = 2일 경우

1부터 4까지의 수 중, 작은 수 부터 시작하여 2개의 수를 중복없이 나열하는 방법은

(1, 2), (1, 3), (1, 4), (2, 1), (2, 3) ... (4, 3) 이다.

 

이를 위해서는 DFS(깊이우선탐색)을 통해 1부터 탐색을 하면 된다.

다만 백트래킹을 통해 방문한 후에는 다시 방문X 처리를 해주어 다음 턴에도 방문할 수 있도록 해야 한다.

 

깊이 4를 예로 들면,

1 -> 2 -> 3 -> 4 의 수열을 만든 후에

1 -> 2 -> 4 -> 3 의 수열을 만들어야 하는데

앞의 3을 방문하고 수열을 만든 후에 방문X 처리를 하지 않으면

1 -> 2 -> 4 의 수열은 3을 방문하지 못하기 때문이다.

 

이렇게 DFS와 백트래킹을 이용하는 방법과

또, 순열(permutation)을 이용하는 방법이 있는데

이 문제의 의도는 백트래킹을 이용하는 것이므로 백트래킹을 이용해 풀어보길 추천한다.

n, m = map(int, input().split())

visited = [False] * (n + 1)
answer = []

def dfs(a):
    if a == 0:
        print(" ".join(map(str, answer)))
        return

    for i in range(1, n + 1):
        if not visited[i]:
            answer.append(i)
            visited[i] = True
            dfs(a - 1)
            answer.pop()
            visited[i] = False


dfs(m)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !