[백준] 15649번 N과 M(1) (java)

<문제>

출처 : https://www.acmicpc.net/problem/15649

<나의 풀이>

import java.util.*;

public class Main {

    static StringBuilder sb = new StringBuilder();	
    // ArrayList 외에도 StringBuilder를 적극 활용해보자.
    static int [] arr;
    static boolean [] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new int[m];
        visited = new boolean[n];

        dfs(n, m, 0);
        System.out.println(sb);
    }

    private static void dfs(int n, int m, int depth) {
        if (depth == m) { // 탈출 조건
            for (int val : arr){
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < n; i++) { // dfs 루프
            if (!visited[i]){
                visited[i] = true;
                arr[depth] = i+1;
                dfs(n,m,depth+1);
                visited[i] = false;
            }
        }
    }
}

참고한 블로그 : https://st-lab.tistory.com/114

<핵심 개념>

백트레킹. 순열, 조합에서 백트레킹이 주로 쓰인다고 한다.
말 그대로 순회를 돌다가 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가 다시 확인하는 절차를 반복해 원하는 값을 찾아내는 알고리즘이다.
한정조건을 갖고 있어 모든 경우를 탐색할 때 보다 효율이 좋다고 한다.
이러한 특성으로 dfs 알고리즘과 함께 쓰이는 경우가 많은데 깊이 우선 탐색으로 끝까지 내려갔다가 조건에 맞지않으면 다시 올라가는 원리이기 때문이다. 그렇기 때문에 넓이를 넓게 탐색하는 bfs 보단 dfs가 더 적합하다.

<피드백>

처음 풀 땐 역시 어렵기 때문에 다른 사람의 코드를 참고해서 풀었다.
하지만 그 마저도 어려워 직접 손코딩으로 따라하며 이해하였던 문제였다.
역시 어려울 땐 손코딩이 최고