백준 [N15649 - N과 M(1)]

전체 소스

public class Main {
    private static int n,m;
    private static int[] arr;
    private static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        visited = new boolean[n+1];
        bt(0);
    }

    public static void bt(int cnt){
        if(cnt == m){
            for(int i : arr) System.out.print(i+" ");
            System.out.println();
            return;
        }

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

 

단계별 문제집의 백트래킹 첫 번째 문제이다.

백트래킹은 유망한 하지 않은 후보 해에 대해 빠르게 포기(가지치기)를 하고 이전 단계(Back Track)로 되돌아가 다른   후보 해를 찾는 알고리즘 기법이다.

개념을 이해해도 직접 코드로 구현하는 것은 어렵다. 다양한 백트래킹 문제를 풀어보며 감을 잡는 게 중요하다.

 

이번 문제의 풀이과정을 차근차근 살펴보며 백트래킹을 이해해보자.

문제를 풀기 위해 필요한 변수 : 

• 입력으로 주어지는 N과 M
• 출력할 수열을 담을 int[] arr = new int[m]배열
• 1~N까지의 자연수 중 방문 여부를 확인할 booelan[] visited = new boolean[n+1]
  왜 n+1인가? 0을 포함해 인덱스 참조를 직관적으로 하기 위해서이다.
  1을 골랐는지는 vistited[1]로 확인할 수 있게 된다.

 

bt(int cnt) 함수 로직 : 

bt(int cnt) 함수로직

dfs는 백트래킹의 일종

 

public static void bt(int cnt){
        if(cnt == m){
            for(int i : arr) System.out.print(i+" ");
            System.out.println();
            return;
        }

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

방문 여부(숫자를 고른 여부)를 확인하고 

방문하지 않았다면 방문처리 후 결과 arr배열에 담는다.

cnt는 깊이와 같은 개념인데 결과 배열에 1개씩 추가될 때마다 cnt+1을 해주어 다음 배열 인덱스에 추가할 수를 또 한 번 재귀 호출하여 구하는 것이다.

이때 cnt가 본래 목표로 했던 m(고를 개수)과 같아진다면 출력을 하고 return 해준다.

return후 이전 함수로 돌아오고(백트래킹) 방문 여부를 false로 다시 지정해 다음에도 고를 수 있도록 해준다.