[백준 15649] N과 M (1) - JAVA

문제 링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

1. 백트래킹(Backtracking)

영단어 그대로 해석해서 '역추적'으로 이해해도 됩니다. 백트래킹(Backtracking)이란 유망성이 존재하는 노드들에 대해서 알고리즘을 적용하는 기법으로, 만일 유망성이 존재하지 않는다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법입니다. 따라서 재귀(Recursion )로 구현할 수 있습니다.

 

모든 경우의 수를 탐색하는 브루트포스(Brute-Force)와 유사해 보이지만 가능성이 없는 경우의 수는 탐색하지 않는다는 점에서 차이가 있습니다.

 

예를 들어 1부터 100까지의 정수에서 50을 넘지 않는 소수 n을 찾아야 하는 문제에서 브루트포스는 100번의 탐색을 수행하는 반면, 백트래킹은 n >= 50이 되는 순간 동작을 멈추게 됩니다.

 

2. 알고리즘

DFS(Depth-First Search)로 알고리즘을 구현하겠습니다.

 

재귀로 구현하고 이미 방문한 노드라면 다음 노드를 탐색하기 위해서(유망성이 있는지 확인하기 위해서) 방문 여부를 저장하는 boolean 배열을 생성하고, 현재의 값을 저장할 int 배열을 생성합니다. 다시 말해, boolean 배열은 중복 여부를 판단하기 위함이고 int 배열은 현재까지 선택된 수열들인 것입니다.

 

재귀를 하면서 문제에서 주어지는 N, M과 재귀의 정도를 나타내는 depth를 매개변수로 넘겨줍니다. 재귀를 1회 수행하면 int 배열에 정수 값이 하나씩 늘어나고, 이를 나타내는 depth에 정수 값 1을 더합니다. depth와 M이 서로 일치하면 문제에서 제시하는 조건을 만족하므로 더 이상 재귀하지 않고 int 배열의 값들을 출력하고 return 합니다.

 

boolean[] visit;
int[] arr;

void dfs(int N, int M, int depth) {
    
    // 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
    if (depth == M) {
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.print("\n");
        return;
    }

    for (int i = 0; i < N; i++) {
    
        // 만약 해당 노드(값)을 방문하지 않았다면?
        if (!visit[i]) {
           visit[i] = true;     // 해당 노드를 방문상태로 변경
           arr[depth] = i+1;    // 해당 깊이를 index로 하여 i + 1 값 저장
           dfs(N, M, depth+1);   // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
           
           // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
           visit[i] = false;
        }
    }
}

 

아래는 전체 코드입니다. 실행속도를 높이기 위해 System.out.println()을 사용하지 않고 StringBuilder를 사용해보았습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class NandM1_15649 {
    private static boolean[] visit;
    private static int[] arr;
    private static StringBuilder result = new StringBuilder();;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(tokens.nextToken());
        int M = Integer.parseInt(tokens.nextToken());
        visit = new boolean[N];
        arr = new int[M];

        dfs(N, M, 0);
        System.out.println(result);
    }

    private static void dfs(int N, int M, int depth) {
        
        // 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
        if (depth == M) {
            for (int val : arr) {
                result.append(val).append(' ');
            }
            result.append('\n');
            return;
        }

        for (int i = 0; i < N; i++) {
            
            // 만약 해당 노드(값)을 방문하지 않았다면?
            if (!visit[i]) {
               visit[i] = true;     // 해당 노드를 방문상태로 변경
               arr[depth] = i+1;    // 해당 깊이를 index로 하여 i + 1 값 저장
               dfs(N, M, depth+1);   // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
               
               // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
               visit[i] = false;
            }
        }
    }
}

 

3. 결과

 

4. 참고

https://st-lab.tistory.com/114

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