[백준]15654-N과M(5) 문제 풀이(Java,자바)

https://www.acmicpc.net/problem/15654

 

들어가며

백트래킹이라고 생각은 했으나 어떻게 구현을 할지 제대로 파악을 못했다.

순열의 개념을 제대로 생각안하고 만들었다가 중복 없는 조합 구하는 코드를 만들었다.

문제를 제대로 생각해야겠다..

 

코드

package solved.ac.class4;

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

public class 백준15654_N과M5 {
    static int n, m;
    static int[] nums;
    static int[] output;
    static boolean[] visited;
    static StringBuilder result = new StringBuilder();
    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());

        nums = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        visited = new boolean[n];
        output = new int[m];
        Arrays.sort(nums);
        search(0);

        System.out.println(result);
    }
    private static void search(int depth){
        if (depth >= m){
            for (int i = 0; i < m; i++){
                result.append(output[i]).append(" ");
            }
            result.append("\n");
            return;
        }

        for (int i = 0; i < n; i++){
            if (!visited[i]){
                visited[i]= true;
                output[depth] = nums[i];
                search(depth+1);
                visited[i]= false;
            }

        }
    }
}

풀이

nums[] - 입력받은 수열

output[] - 중간중간마다 만들어진 순열을 저장하는 곳

visited[] - 수열을 돌아다닐 때, 방문한 곳인지 파악하기 -> 중복 제거를 위함

 

Arrays.sort(nums);

 

잊지 말아야 할 것은 사전 순 정렬이다.

 

private static void search(int depth){
    if (depth >= m){
        for (int i = 0; i < m; i++){
            result.append(output[i]).append(" ");
        }
        result.append("\n");
        return;
    }

    for (int i = 0; i < n; i++){
        if (!visited[i]){
            visited[i]= true;
            output[depth] = nums[i];
            search(depth+1);
            visited[i]= false;
        }

    }
}

제일 중요한 순열 찾는 백트래킹 메서드다.

현재 위치를 depth라고 생각한다.

그리고 뽑고자 한 수인 m에 도달하면 output에 있는 모든 값을 꺼내서 따로 저장한다.

이게 찾고자 했던 순열인 것이다.

output[depth] = nums[i];
search(depth+1);

output[] 배열이 하나임에도 불구하고 모든 상태를 다 저장할 수 있는 이유는 재귀가 끝나고 다음 반복문을 실행할 때, 덮어쓰기 때문이다.

 

for (int i = 0; i < n; i++){
    if (!visited[i]){
        visited[i]= true;
        output[depth] = nums[i];
        search(depth+1);
        visited[i]= false;
    }
}

그러면 왜 수열의 첫번째부터 반복문을 돌리는 것일까??

이건 순열을 구하기 위함이다.

1,2

1,3

구하다가 두번째 숫자인 2에 도달하게 되면 2,1과 같은 이전 값이 필요하다.

그래서 i = 0부터 시작하고 중복도 체크하기 위해 visited[]를 사용하는 것이다.