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

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

15650번: N과 M (2)

문제 설명

• 자연수 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) 이다.

이 때, (2, 1), (3, 1), (3, 2) ... 는 오름차순이 아니기 때문에 제외해야 한다.

 

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

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

 

깊이 3를 예로 들면,

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

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

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

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

 

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

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

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

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

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


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

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


dfs(1, m)

https://github.com/HongEunho

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

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