[백준] 10974: 모든 순열 (JAVA)

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력 1

3

예제 출력 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

풀이

바로 직전에 순열을 사용한 문제를 풀어서 나름 수월하게 푼 문제였다.

주의할 점은 한번 백트래킹을 돌릴 때마다 visited뿐만 아니라 sb도 초기화 해줘야 한다는 점이다.

 

정답 코드

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

public class Main {
    static int N;
    static boolean[] visited;
    static StringBuilder ans = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        visited = new boolean[N+1];
        permutation(0, new StringBuilder());
        System.out.println(ans);
    }

    static void permutation(int index, StringBuilder sb) {
        if (index == N) {
            sb.delete(sb.length()-1, sb.length()); // 공백 제거
            ans.append(sb).append('\n');
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int len = sb.length();
                sb.append(i);
                permutation(index + 1, sb.append(" "));
                sb.delete(len, sb.length());
                visited[i] = false;
            }
        }
    }
}