[Java+Python]15650번, N과 M(2), 조합

Java+Python으로 순열/조합/중복순열/중복조합 구현하기

 

[Java+Python]15649번, N과 M(1), 순열

[Java+Python]15650번, N과 M(2), 조합

[Java+Python]15651번, N과 M(3), 중복순열

[Java+Python]15652번, N과 M(4), 중복조합

 

문제

 

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 

중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이

 

지난번 문제가 순열을 구하는 문제였다면, 이번 문제는 조합을 출력하는 문제이다.

 

순열과 조합의 차이는 예를 들자면 (1, 2)와 (2, 1)을 다른 것으로 보느냐(순열), 그렇지 않으냐(조합)의 차이다.

 

그러니까 조합에서는 (1, 2)와 (2, 1)이 같은 경우이므로, 해당 노드를 방문할 필요가 사라지게 된다.

 

조금 더 상세하게 말하자면, 1이 들어간 모든 순서쌍은 처음 1에 대해 순회할 때 모두 뽑을 테니

 

다음 순회 시에는 2부터 시작해 그보다 큰 노드만 순회하면 된다는 뜻이다.

 

이는 15649번의 코드를 살짝만 고쳐 이룩할 수 있다.

 

먼저 자바 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Prob15650 {

	static int n;
	static int m;
	static int[] arr;
	static boolean[] isVisited;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		isVisited = new boolean[n + 1];

		dfs(1, 0);

	}

	private static void dfs(int start, int depth) {
		if (depth == m) {
			for (int num : arr) {
				System.out.print(num + " ");
			}
			System.out.println();
			return;
		}

		for (int i = start; i <= n; i++) {
			if (!isVisited[i]) {
				isVisited[i] = true;
				arr[depth] = i;
				dfs(i, depth + 1);
				isVisited[i] = false;
			}
		}
	}
}

이어서 파이썬.

 

참고로 이 문제는 유독 파이썬에서 효율이 좋았다.

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())

lst = [0 for _ in range(m)]
isVisited = [False] * (n + 1)


def dfs(start, depth):
    if depth == m:
        for num in lst:
            print(num, '', end='')
        print()
        return

    for i in range(start, n + 1):
        if isVisited[i] is False:
            isVisited[i] = True
            lst[depth] = i
            dfs(i, depth + 1)
            isVisited[i] = False


dfs(1, 0)