[Java] 백준(실버-3) 15649번 - N과 M(1)

문제 풀이

---

이 문제는 재귀 알고리즘 중 하나인 백트래킹 기법을 이용하여 풀 수 있다.

아이디어 도출

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구해야 하는데, 중복 없이 M개의 순서에 따라 선택한 수열을 구해야 한다. 이 때, DFS를 활용한 재귀 안에서 가지치기를 하는 방식으로 백트래킹을 이용할 수 있다.

첫번째 올 수 있는 수 N가지
두번째 올 수 있는 수 N-1가지
.
.
.
마지막에 올 수 있는수 1개

위와 같이 N! 경우의 수를 가지게 된다. 이를 통해 아이디어를 생각해보면 다음과 같다.

• DFS를 이용해 특정한 위치에 올 수 있는 수를 결정할지 모든 경우의 수를 탐색한다.
• 올 수 있는 수는 1 ~ N까지의 수 중에서 앞서 선택하지 않은 수를 구한다. 이 과정이 백트래킹에 해당된다.
• 결국, 모든 위치에서 재귀함수를 호출하여 이 과정을 반복하며 깊이(위치)가 M이 된다면 선택해서 채운 수열을 출력하면 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    // 입력 N, M 선언
    static int N, M;
    
    // 방문 배열과 수열을 담을 배열 선언
    static boolean[] visited;
    static int[] arr;
    
    // 결과를 담아 출력할 StringBuiler 객체
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 방문 배열과 수열을 담을 배열 초기화
        visited = new boolean[N+1];
        arr = new int[N+1];

        // 재귀함수 호출
        recursion(0);

        // 재귀함수에서 담아낸 수열 출력
        bw.write(sb+"\n");

        bw.close();
        br.close();
    }

    /**
     * 백트래킹 재귀함수
     * DFS의 depth와 유사한 역할을 하는 idx를 인자로 받는다.
     * idx가 M과 같다면 재귀를 종료한다.
     */
    static void recursion(int idx) {
        // idx가 마지막 위치인 M이 된다면 수열을 출력하기 위해 재귀를 종료
        if(idx == M) {
            for(int i=0; i<M; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        // 1부터 N까지의 수를 선택해나가며 백트래킹을 진행한다.
        // [1,X], [2,X], [3,X]와 같은 방식으로 재귀호출이 된다.
        // 선택(사용)되지 않을 수일 경우에 방문 여부를 체크한 후,
        // arr 배열의 다음 칸을 채우기 위해 idx+1로 재귀함수를 호출한다.
        // recursion 함수 호출이 수행된 후, 방문 여부를 다시 해제한다.
        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[idx] = i;
                recursion(idx + 1);
                visited[i] = false;
            }
        }
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.