15663번

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

15663번: N과 M (9)

이 문제는 중복되는 수열의 출력을 제거하고, 나올 수 있는 모든 수열을 출력하는 문제이다. 즉, 자기자신이 두 번 출력되는 것을 없애고, 나머지를 출력하는 것이다.

이 문제를 해결하기 위해서는 매번 메서드를 호출할 때마다 중복을 검사해줘야한다.

중복을 검사하는 방법은 방문했던 값인가, 이전의 값과 같은 값인가를 비교하는 방법인 두 가지로 이루어진다.

아래의 코드를 보면 이해가 빠를 것이다.

public void dfs(int depth){
    if(depth==m){
        for(int i:ans){
            sb.append(i).append(" ");
        }
        sb.append("\n");
        return;
    }
    int tmp=0;
    for(int i=0; i<n; i++){
        if(check[i] || tmp == arr[i]){
            continue;
        }
        ans[depth] = arr[i];
        check[i]=true;
        tmp = arr[i];
        dfs(depth+1);
        check[i]=false;
    }
}

예를 들어 3 2 \n 9 9 1이라고 입력이 들어왔다고 가정해보자.

그럼 i=0일때 1이 들어오고 그 다음 재귀함수가 실행되어 깊이가 1인 곳에 9가 들어오고 tmp에는 9가 기록된다. 그럼 깊이 2로 증가시켜 출력을 하고, 다시 깊이가 1인 곳에 돌아와서 9의 방문을 false로 만든다. 그럼 여기서 tmp에는 9가 기록되어있다.

그렇기 때문에 다음 값인 9를 방문해도 tmp값과 같기 때문에 무시하고 지나간다. 그럼이제 깊이가 0인 곳으로 돌아온다.

여기서 이번에는 i=1이 되어, 9를 집어넣고, 재귀함수 안으로 들어가면 깊이가 1이고,i=0인 1을 방문한다. 그럼 깊이가 2가되고, 재귀함수를 들어가면 깊이가 2가 되면서 출력한다.

그리고 1의 방문을 false로 돌리고, tmp에는 1이 기록되어있다. 그럼 그 다음 i=1인 9를 방문하고, 깊이가 2가된다. 그 다음 재귀함수를 들어가면 깊이는 2가 되면서 출력한다. 그럼 1 9, 9 1, 9 9가 출력된다.

즉, 1일때는 깊이 0에서 tmp=1 깊이 1에서 tmp=9

     9일때는 깊이 0에서 tmp=9 깊이 1에서 tmp=1

이기 때문에 9 9값이 나올 수 있다.

 

처음에 이 문제를 접했을 때 중복처리를 어찌할지 방법을 몰라서 질문게시판을 참고했다...

 

정답 코드는 아래와 같다.

package backjoon.b15663;
import java.io.*;
import java.util.*;
public class b15663 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        Graph g = new Graph(n,m,arr);
        g.dfs(0);
        System.out.println(g.sb);
    }
}
class Graph{
    int n;
    int m;
    int[] arr;
    boolean[] check;
    int[] ans;
    StringBuilder sb;
    public Graph(int n, int m, int[] arr) {
        this.n = n;
        this.m = m;
        this.arr = arr;
        ans = new int[m];
        check = new boolean[n];
        sb = new StringBuilder();
    }

    public void dfs(int depth){
        if(depth==m){
            for(int i:ans){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        int tmp=0;
        for(int i=0; i<n; i++){
            if(check[i] || tmp == arr[i]){
                continue;
            }
            ans[depth] = arr[i];
            check[i]=true;
            tmp = arr[i];
            dfs(depth+1);
            check[i]=false;
        }
    }
}