[알고리즘 PS] 백준 15649번 N과 M (1) 자바 문제풀이

문제

해당 포스팅은 백준의 N과 M (1) 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

 

이번 문제는 백트래킹 문제의 대표적인 문제라고 할 수 있다.

이전 시간까지 우리는 브루트 포스 알고리즘 문제들을 풀었는데, 브루트 포스 알고리즘은 가능한 모든 경우를 대입해 정답을 찾는 방식이다.

하지만 이번 문제에서 브루트 포스 알고리즘이 아닌 백 트래킹 알고리즘이 더욱 잘 어울려 보인다.

Back-Tracking 알고리즘

백트래킹은 노드의 유망성을 판단한다.

여기서 노드의 유망성이라고 함은 쉽게 가지치기라고도 불리며 흔한 예로 dfs에서 방문 했는지를 확인하는 boolean[] check 에 해당한다.

여기서 노드의 유망성을 확인하고 만약 유망하지 않은 노드라면 해당 탐색은 더 깊게 들어가지 않고 다른 탐색으로 진행하게 된다.

 

이 방법이 바로 모든 경우를 다 시도하는 브루트 포스와 다른점이라고 할 수 있는데, 해당 문제에서는 이러한 점을 이용하여 문제를 해결할 수 있다.

해결법

우선 문제에서 하고자 하는 말을 찾아보자.

1~N 까지 수를 중복 없이 M개 뽑을 수 있는 모든 경우의 수

예를 들어 N과 M이 각각 3이라고 가정해보자.

그럼 위와 같이 중복이 없는 경우의 수를 트리와 같이 나타낼 수 있다.

 

여기에 백트래킹 알고리즘을 적용해보자.

 

노드의 유망성은 무엇일까?

그렇다 바로 중복이 아닌 노드가 노드의 유망성이 된다.

우리는 유망성을 판단하기 위한 boolean[] check 배열을 만들고 탐색 과정에서 결과 값을 담을 int[] arr를 생성하여 이용할 것이다.

 

이 문제는 dfs로 해결할 것이며, N과 M을 받는 변수와 Index 변수를 통해서 재귀가 깊어질 때 마다 1씩 증가하는 재귀 함수를 구현한다.

 

그리고 Index 변수가 m과 같아진다면 호출을 끝내고 탐색 과정에서 저장한 arr 값을 출력하여 마무리하면 된다.

오답 후보

만약 check[i] 의 값을 다시 false로 지정하지 않는다면 모든 노드에 대해서 dfs가 되지 않을 것이다.

 

즉 처음 실행한 dfs만 출력이 될 것이다.

 

우리는 모든 노드를 dfs해야 하기 때문에 해당 노드로 시작한 dfs의 탐색이 끝난다면 다른 노드도 탐색할 수 있도록 false로 초기화 해주어야 한다.

정답 코드

public class Main {
    static boolean[] check = new boolean[10];
    static int[] graph = new int[10];
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int m = input.nextInt();

        dfs(0, n, m);
    }

    private static void dfs(int index, int n, int m) {
    
        if(index == m) {
        
            for(int value : graph) {
            
                if(value != 0) System.out.print(value + " ");
            }
            
            System.out.println();
            
            return ;
            
        }

        for (int i = 1; i <= n; i++) {
        
            if(check[i]) continue;
            
            check[i] = true;
            
            graph[index] = i;
            
            dfs(index + 1, n, m);
            
            check[i] = false;
        }
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.