https://www.acmicpc.net/problem/10974
문제
> N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.접근
1부터 N까지 중 모든 수를 사용해서 가능한 모든 경우의 수열을 만든다.
기존 백트래킹에서 특정 인덱스번째로 재귀로 넘겼다면 1부터N까지에 대해 boolean형 배열을 만들어 사용한 수를 마킹하며 매 재귀마다 N까지의 범위 중 마킹이 안된(사용안한)수 중 골라서 사용한다.
문제해결
> N을 입력받고 만든 수열을 저장할 배열 num을 N의 크기로 만든다.
> 사용한 수를 마킹하기 위한 boolean형 배열 visited를 1-based로 만든다.
> 아직 쓴 수가 없으므로 초기값으로 false 지정해주고 per메소드에 아직 고른수가 없으므로 0을 넘겨 호출한다.
> per메소드에선 백트래킹으로 수열을 만든다.
> 탈출 조건으로 수열의 크기가 N이 되면(num은 0-based) 재귀를 깨고 저장된 수열을 출력한다.
> 아니라면 매 재귀마다 1부터 N까지 가능한 수를 탐색한다.
> visited에 true인 수는 사용한 수이므로 넘어가고 안쓴수는 마킹해주고 결과 배열에 넣으며 재귀로 다음 수를 뽑는다.
> 재귀가 깨져 돌아오면 해당 번째에 썼던 수를 다른 번째에 쓸 수 있도록 마킹을 다시 false로 돌려놓는다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//10974번 모든 순열
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N;
static boolean[] visited;
static int[] num;
public static void per(int rst) {
if(rst == N) {
for(int i : num) sb.append(i).append(' ');
sb.append('\n');
return;
}
for(int i = 1; i <= N; i++) {
if(visited[i]) continue;
visited[i] = true;
num[rst] = i;
per(rst+1);
visited[i] = false;
}
}
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
num = new int[N];
visited = new boolean[N+1];
Arrays.fill(visited, false);
per(0);
System.out.print(sb);
}
}
후기
기존 NtoM문제들 말고 다른 백트래킹을 풀었는데 확실히 조금 다르지만 가닥이 비슷해서 어렵지 않았다.
