[BOJ] 백준 15649 N과 M (1)

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

 Input 
4 2　 

 Output 

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3　

중복 없는 순열을 구현하는 문제

- 방문 표시 변수 활용 ( boolean[] visited )

- 재귀함수 이용

 

▶ 순열과 조합 (백준 N과 M 시리즈) 

순열과 조합 (백준 N과 M 시리즈)

---

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) {
        if (visited[i]) continue;
        visited[i] = true;
        ans[depth] = i + 1;
        DFS(depth + 1);
        visited[i] = false;
    }
}

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

 

Java

import java.util.Scanner;
 
public class Main {
      
    static int[] arr, output;
    static boolean[] visited;
    static int N, M;
      
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
         
        N = Integer.parseInt(sc.next());
        M = Integer.parseInt(sc.next());
         
        arr = new int[N+1];
        // 뽑힌 순서를 알아내기 위한 배열
        output = new int[N+1];
        visited = new boolean[N+1];
         
        for(int i=1; i<= N; i++) {
          arr[i] = i;
        }
         
        permutation(1);
 
    }
    private static void permutation(int idx) {
           
          // 만약 원하는 길이만큼 구성되었다면 리스트에  담아둔다.  
          if(idx > M) {
              // 지금까지 방문한(뽑힌) 원소를 출력한다.
              for(int i=1; i<= M; i++) {
                   System.out.print(output[i] + " ");
              }
              System.out.println();
              return;
          }
           
          // 중복을 제외하기 위해서 방문하지 않았던 원소를  한개씩 추출한다.
          for(int i=1; i<= N; i++) {
              if(!visited[i]) {
                   // 해당 원소를 뽑았다는 의미 방문표시
                   visited[i] = true;
                   // 뽑은 원소를 결과값에 대입시킨다.
                   output[idx] = arr[i];
                   // 다음 자리의 문자열을 재귀로 탐색해서  채워간다.
                   permutation(idx + 1);
                   // 재귀로 쭈욱 채워지고 호출이 끝났을 때  
                   // 해당 숫자의 방문표시(사용여부)를 초기화 해줘야 한다.
 
                   // 다음 자리 수를 채울 수 있다.
                   visited[i] = false;
              }
          } 
     }
}