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

문제

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

15650번: N과 M (2)

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

문제 접근

이번 문제는 지난 N과 M (1) 풀이와 마찬가지로 백트래킹 문제의 대표적인 문제라고 할 수 있다.

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

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

Back-Tracking 알고리즘

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

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

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

 

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

 

지난 N과 M (1) 풀이에서는 중복이 없는 수를 위해서 유망 조건을 check[i] == false 인 값만 탐색하도록 했는데, 이번 문제에서는 한 가지를 더 해야 한다.

고른 수열이 오름차순이어야 한다.

다음 두 수를 봐보자.

• 1 3 2 4
• 1 2 3 4

여기서 1 3 2 4는 수열 자체가 오름 차순이 아니므로 탈락하게 된다.

 

이걸 어떻게 구현할까?

해결법

우리는 여기서 유망 조건을 하나 더 추가할 것인데, 바로 지난번 사용한 인덱스 값이 현재 값보다 작을 경우 가지치기를 할 것이다.

 

그러기 위해서는 지난번 사용한 인덱스 값을 알려줄 매개변수 하나를 추가해야한다.

dfs(int index, int n, int m, int before);

before = result[index];

 

정답 코드

private static void dfs(int index, int n, int m, int before) {
    if(index == m) {
        for (int i = 0; i < 8; i++) {
            if(result[i] != 0) {
                System.out.print(result[i] + " ");
            }
        }
        System.out.println();
        return;
    }

    for (int i = 1; i <= n; i++) {
        if(check[i] || i < before) continue; // 유망성 판단 조건 1, 2
        check[i] = true;
        result[index] = i;
        dfs(index + 1, n, m, result[index]);
        check[i] = false;
    }
}

내가 구현한 dfs는 이렇다.

하지만 여기서 더 효율적으로 최적화 시킬 수 있다.

 

다음 인덱스를 채우기 위한 for문을 보면, i가 1부터 시작해서 유망성 판단 조건 1, 2를 거치게 할 게 아니라 애초에 유망성 판단 조건 2번을 만족하는 수만 채우면 조건 하나를 덜 사용하고 그만큼 시간도 최적화될 수 있다.

 

private static void dfs(int index, int n, int m, int before) {
    if(index == m) {
        for (int i = 0; i < 8; i++) {
            if(result[i] != 0) {
                System.out.print(result[i] + " ");
            }
        }
        System.out.println();
        return;
    }

    for (int i = before; i <= n; i++) { // 아예 시작을 유망한 노드들부터 해버리면 됨
        if(check[i]) continue; // 유망성 판단 조건 1
        check[i] = true;
        result[index] = i;
        dfs(index + 1, n, m, result[index]);
        check[i] = false;
    }
}

그럼 시간을 조금 더 단축할 수 있다.

 

 

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