[BOJ] 백준 15651 N과 M(3)

출처: https://www.acmicpc.net/problem/15651

 Input 
4 2

 Output 

1 1

1 2

1 3

1 4

2 1

2 2

2 3

2 4

3 1

3 2

3 3

3 4

4 1

4 2

4 3

4 4

중복 되지 않는 순열 문제 [BOJ] 15649 N과 M (1)와 차이는 vistied[]를 제거한 부분이다.

즉, 방문 표시가 없으므로 재방문이 가능해져서 "중복 가능한 순열"이 된다.

 

※ 이 문제에서는 출력속도를 맞추기 위해 BufferedWriter 이용

---

C / C++

#include <stdio.h>

const int MAX_N = 8 + 2;
int N, M, ans[MAX_N];
bool visited[MAX_N];

void DFS(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < N; ++i) {
        ans[depth] = i + 1;
        DFS(depth + 1);
        ans[depth] = 0;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    DFS(0);
}

 

Java

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;
 
public class Main {
 
    static int[] arr, output;
    static int N, M;
    static BufferedWriter log;
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        log = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(sc.next());
        M = Integer.parseInt(sc.next());
 
        arr = new int[N + 1];
        // 뽑힌 순서를 알아내기 위한 배열
        output = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
            arr[i] = i;
        }
 
        permutation(1);
        log.flush();
    }
 
    private static void permutation(int idx) throws Exception {
        // 원하는 길이만큼 구성되었다면 리스트에 담아둔다.
        if (idx > M) {
            // 지금까지 방문한(뽑힌) 원소를 출력한다.
            for (int i = 1; i <= M; i++) {
                log.write(output[i] + " ");
            }
            log.write("\n");
            return;
        }
 
        for (int i = 1; i <= N; i++) {
            // 뽑은 원소를 결과값에 대입시킨다.
            output[idx] = arr[i];
            // 다음 자리의 문자열을 재귀로 탐색해서 채워간다.
            permutation(idx + 1);
        }
 
    }
}