[백준/Java] 10974 모든 순열

문제

https://www.acmicpc.net/problem/10974

풀이방법

비트마스킹을 사용하여 visited 배열없이 풀기...

풀이

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] result = new int[N];
        boolean[] visited = new boolean[N + 1];

        backtracking(N, 0, result, visited);
    }
    static void backtracking(int N, int depth, int[] result, boolean[] visited ) {
        if (depth == N) {
            for(int i = 0; i<N; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i<=N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = i;
                backtracking(N, depth + 1, result, visited);
                visited[i] = false;
            }
        }
    }
}

 

비트마스킹 이용

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] result = new int[N];

        backtracking(N, 0, 0, result);
    }
    static void backtracking(int N, int depth, int bitmask, int[] result) {
        if (depth == N) {
            for(int i = 0; i<N; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i<=N; i++) {
            if ((bitmask & (1<<i))==0) { //bitmask시 &연산했을 때 0은 미사용, 1은 사용 i번째 사용했는지 확인
                result[depth] = i;
                backtracking(N, depth + 1,bitmask| 1<<i, result); // i번째 사용했음
                //bitmask를 변경 후 전달하는 것이 아니라 새로운 호출에 넘겼으므로 다시 복원 과정 필요없음
            }
        }
    }
}