[ 백준 14534번 ] String Permutation

1. 문제

14534번: String Permutation

 

2. 풀이

 

백트래킹의 가장 기본적인 유형인 순열 만들기 문제다. 집합의 요소를 사용했는지를 판단할 boolean 배열을 선언하여, 각 요소들의 사용여부를 변경해가며 순열을 만들면 해결할 수 있다.

 

다만 현재 문제는 조합(Combination)이 아닌 순열(Permutation)이므로, 백트래킹을 할 재귀 함수 내에서 시작지점은 항상 첫 요소로 설정해야 한다. 시작지점부터 앞서 선언한 boolean 배열을 통해 사용하지 않은 요소가 있다면 사용하여 재귀를 돌리고, 다시 사용하지 않겠다고 선언하여 다른 경우의 수를 체크하는 것이다.

 

3. 소스코드

public class Main {

    static char[] line;

    static void permutation(int len, String str, boolean[] visit) {
        if (len == line.length) {
            System.out.println(str);
            return;
        }

        for (int i = 0, n = line.length; i < n; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            permutation(len + 1, str + line[i], visit);
            visit[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        for (int i = 1; i <= N; i++) {
            line = br.readLine().toCharArray();

            System.out.printf("Case # %d:\n", i);
            permutation(0, "", new boolean[line.length]);
        }

        br.close();
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code