(알고리즘) N과 M (1) - 순열

www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

문제 설명

순열에 대한 문제이다.

이전 포스팅에서 언급하였다시피 순열은 순서가 있는 배열이며 DFS를 사용하여 풀이를 할 수 있다.

jwdeveloper.tistory.com/270

(알고리즘) 순열과 조합의 차이

 

방문 노드를 설정하여 노드 방문 시 체크를 하고 노드의 탐색이 끝나면 방문을 초기화하며 다음 노드를 탐색한다.

(depth를 가지고 다니며 탐색)

또한 노드에서 뽑아야 하는 수를 다 뽑으면 종료시킨다. 

필자는 재귀에 대한 순서가 헷갈려서 그림으로 본 후에야 이해했다.
위의 그림처럼 2개의 순열을 뽑는다고 가정해보자
dfs(0)부터 시작해서 1부터 3까지의 depth로 루프를 돈다.
이때 주의할 점이 루프안에 재귀가 있다는 재귀가 있다는 점이다. 그리고 재귀의 호출을 끝내고 방문을 false로 초기화한다.

dfs(0) -> dfs(1) -> dfs(2) -> dfs(3)으로 이어지고

먼저 dfs(1) 에서 depth를 +1 하면서 1번에 대한 경우의 수 [1, 2] [1, 3]를 모두 체크하고 방문을 초기화한 뒤에
(for문에서 1번은 이제 끝) 다시 dfs(1)재귀에서 다음 인덱스인 2를 동일한 과정으로 체크한다.
이 과정을 반복하면 
1 ~ 3 까지의 모든 경우의 수를 순서가 있도록 체크가 가능하다.

 

코드

public class Problem_15649 {
    private static int n;
    private static int m;
    private static boolean[] visited;
    private static int[] arr;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        visited = new boolean[n+1];
        arr = new int[m];

        dfs(0);

    }

    private static void dfs(int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();

            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                arr[depth] = i;
                visited[i] = true;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

---

Code Link

github.com/mike6321/Algorithm/blob/master/Algorithm/src/main/java/me/choi/book/e_problem/nandm/Problem_15649.java

mike6321/Algorithm

References

st-lab.tistory.com/114

[백준] 15649번 : N과 M (1) - JAVA [자바]