#15649 : N과 M (1)

풀이방법

사용된 것:

백트래킹(backtracking)

Deque

 

 

 

 

 

2023.01.17

숫자를 순서대로 하나 고르는 것을 한 번의 단계로 본다.

사전순 순서에 맞추어 숫자를 하나하나 고르면서, 백트래킹을 통해 모든 수열을 찾는다.

 

코드

Java(2023.01.17)

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	static StringBuilder sb;
	static boolean[] visited;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		sb = new StringBuilder();
		
		Scanner sc = new Scanner (System.in);
		
		//N과 M의 값 읽어오기
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		//덱 선언
		Deque<Integer> deque = new LinkedList<Integer>();
		
		for(int i=1; i<=n; i++) {
			visited = new boolean[n+1];	//visited 배열 선언
			solve(n, m, 0, i, deque);	//문제 해결
		}
		
		//정답 출력
		System.out.print(sb);
		
		sc.close();

	}
	
	static void solve(int n, int m, int cnt, int cur, Deque<Integer> deque) {
		//이미 고른 적 있는 수라면 아무것도 하지 않고 즉시 리턴
		if(visited[cur]) return;
		
		//수 추가, cnt 1 증가
		visited[cur] = true;
		deque.add(cur);
		cnt++;
		
		//추가 후 현재 cnt 값이 M과 같다면
		//덱에 들어있는 모든 수를 sb에 순서대로 추가
		if(cnt == m) {
			for(int i=0; i<m; i++) {
				int temp = deque.pollFirst();
				sb.append(temp + " ");
				deque.add(temp);
			}
			sb.append(System.lineSeparator());
		}
		
		
		//추가 후 현재 cnt 값이 M보다 작다면
		//재귀를 통해 다음 수를 선택
		else {
			for(int i=1; i<=n; i++) {
				solve(n, m, cnt, i, deque);
			}
		}
		
		//이 state에서 할 일이 모두 끝났으므로 백트래킹
		visited[cur] = false;
		deque.pollLast();
		return;
	}

}