[JAVA] 백준10974 모든 순열

문제 링크

---

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

10974번: 모든 순열

 

 

접근 및 시도 (생각의 흐름)

---

DFS를 통한 순열, 조합 문제를 더 풀어보자 라고 찾아보다가 발견한 문제.

 

 

 

사용 알고리즘

---

- DFS 순열

 

 

풀이

---

- 순열은 조합과 달리 idx가 필요 없다.

- 순열은 조합과 달리 selected 된 순서대로 값을 저장할 배열, ArrayList 등의 자료구조가 더 필요하다.

 

ex)

<조합>

    public static void dfs(int idx, int cnt, int n) {
        if (cnt == n) {
            check();
            return;
        }

        for (int i = idx ; i < N ; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            dfs(idx + 1, cnt + 1, n);
            visited[i] = false;
        }
    }

 

<순열>

    public static void dfs(int cnt, int n) {
       if (cnt == n) {
            print();
            return;
        }

        for (int i = 0 ; i < N ; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            selected.add(cnt, b[i]);
            dfs(cnt + 1, n);
            visited[i] = false;
            selected.remove(cnt);
        }
    }

 

	조합	순열
idx	dfs 함수 내부의 for-loop을 아래와 같이 idx 부터 돈다 for (int i = idx ; i < chicken.size() ; i++) { } 만약 시작점이 2라면 조합에서는 {2, 3, 1} = {1, 2, 3} 이 동일하다. 따라서 2 이전에 나온 1에 대해서는 고려하지 않아도 된다.	dfs 함수 내부의 for-loop을 아래와 같이 처음부터 돈다 for (int i = 0 ; i < N ; i++) { } 만약 시작점이 2라면 순열에서는 {2, 3, 1} != {1, 2, 3} 이 다르다. 따라서 2가 시작점인 순간 1도 고려해서 순열을 계산한다.
추가적인 자료구조	없음	순열을 순서대로 저장할 selected 배열 또는 ArrayList 필요

 

 

총평

---

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static int[] b;
    static boolean[] visited;
    static int N;
    static ArrayList<Integer> selected = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        b = new int[N];
        visited = new boolean[N];

        for (int i = 0 ; i < N ; i++) {
            b[i] = i+1;
        }

        dfs(0, N);
    }

    public static void dfs(int cnt, int n) {
        if (cnt == n) {
            print();
            return;
        }

        for (int i = 0 ; i < N ; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            selected.add(cnt, b[i]);
            dfs(cnt + 1, n);
            visited[i] = false;
            selected.remove(cnt);
        }
    }

    public static void print() {
        for (int i = 0 ; i < N ; i++) {
            System.out.print(selected.get(i)+" ");
        }
        System.out.println();
    }
}