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

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)

 

출력

 

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

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

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

 

풀이

 

전형적인 DFS문제이자, 주어진 숫자로 순열을 만드는 문제이다.

 

기존에 풀이할 때는 순열, 조합, 중복순열, 중복조합 메서드를 미리 만들어두고 

 

문제에 따라 사용했는데, 다시 푸는 김에 DFS를 이용해서 최대한 간결하게 풀기로 했다.

 

심지어 파이썬은 순열과 조합을 구하는 함수가 내장되어 있는 것 같기도 하던데..

 

그런 거 없고 여러 문제에 응용할 수 있게 DFS 구현해 놓기.

 

먼저 자바 코드이다.

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

public class Prob15649_4 {

	static int n;
	static int m;
	static int[] arr;
	static boolean[] isVisited;
	static StringBuilder sb = new StringBuilder();

	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(0);

		System.out.println(sb);
	}

	private static void dfs(int depth) {
		if (depth == m) {
			for (int num : arr) {
				sb.append(num).append(' ');
			}
			sb.append('\n');
			return;
		}

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

이어서 파이썬 코드.

 

파이썬은 순열과 조합을 구하는 함수가 내장되어 있는 것 같지만,

 

당연히 그렇게 풀라는 문제는 아닌 것 같으니 간결한 DFS로 풀어보았다.

import sys

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

arr = [0] * m
isVisited = [False] * (n + 1)


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

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


dfs(0)

 

전역변수를 선언하지 않고 풀어보고 싶었지만 도저히 내 머리로는 되지 않는다.

 

기존에 따로 구현했던 메서드에 비해 확실히 짧아진 느낌!

 

참고로 시간도 1/4로 줄었다.