15649번 N과 M(1)

실버3 - 백트래킹

소스 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static boolean[] visited;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            visited = new boolean[N];
            arr = new int[M];

            DFS(0);

            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static void DFS(int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

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

---

풀이 방법

백트래킹..?? 뭔데 그게.. 뒤에서부터 확인하는거 뭐 그런거야??

일단 뭔지 모르고 막 풀어보려고 했는데 단순하게 반복문만 사용하려고 하니 제대로 되지 않았다...

알고리즘도 공부할 겸 풀이를 확인했다.

즉, 백트래킹 = DFS가 아니라 백트래킹의 방법 중 하나가 DFS인 것이다

!? 백트래킹 문제를 DFS를 사용해서 풀 수 있구나!! (BFS를 사용해서도 풀 수 있다고 한다.)

코드를 보니 상당히 쉽게 이해가 됐다...
재귀적으로 호출하는 DFS(depth + 1) 이 끝나고 나면 visited[i] = false 로 다시 바꿔준다는 것을 잊지 말자!

그래야 재귀가 끝나고 다음 순서를 제대로 탐색할 수 있다.

0 1 / 0 2 / 0 3 을 탐색한 이후에 1 0 / 1 1 / ... 으로 탐색해야 하는데 1을 탐색한 후에 visited[1] = false로 바꿔놓지 않으면 1 0 은 탐색을 하지 못한다.

자세한 설명은 항상 신세지고 있는 Staranger's LAB님 블로그에서 확인!