백준 15663번 : N과 M (9) java

이 문제는 dfs를 이용한 백트래킹 문제입니다.

이 문제를 풀 때 유의해야 하는 것은 중복되는 입력이 있을 수 있고 중복되는 수열을 여러 번 출력하면 안 된다는 것입니다.

코드를 보면서 설명 드리겠습니다.

---

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

public class Main {
    static int[] numArr;
    static int[] out;
    static boolean[] visited;
    static int M;
    static int N;

    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());

        numArr = new int[N];
        visited = new boolean[N];
        out = new int[M];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
            numArr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(numArr);

        dfs(0);
    }

    static void dfs(int cnt){
        if(cnt == M){
            for(int i = 0; i<M; i++)
                System.out.print(out[i]+" ");
            System.out.println();
        }

        else{
            int before = 0;
            for(int i = 0; i<N; i++){
                if(visited[i])
                    continue;

                if(before != numArr[i]){
                    visited[i] = true;
                    out[cnt] = numArr[i];
                    before = numArr[i];
                    dfs(cnt+1);
                    visited[i] = false;
                }
            }
        }
    }
}

dfs를 이용해서 다른 N과 M 문제와 같이 풀었습니다.

다른 N과 M 문제들과 는 다른 점은 아래와 같은 코드입니다.

else{
    int before = 0;
    for(int i = 0; i<N; i++){
        if(visited[i])
            continue;

        if(before != numArr[i]){
            visited[i] = true;
            out[cnt] = numArr[i];
            before = numArr[i];
            dfs(cnt+1);
            visited[i] = false;
        }
    }
}

여기서 before라는 변수를 사용한 것이 보일 것입니다.

이 문제에서는 중복된 수열을 출력할 때 1번은 출력하고 그다음부터 중복된 수열들을 출력하면 안 됩니다.

이렇기 때문에 Arrays.sort를 통해 정렬된 배열이 있을 때 단순히 numArr[i] == numArr[i-1]일 때 continue를 하면 안됩니다.

따라서 for문이 시작될 때 before이라는 변수를 선언하고 그 for문을 돌 때 이전에 중복된 것이 있었는가를 확인합니다.

이 과정을 그림으로 보여드리겠습니다.

예제 2번을 예시로 두었을 때 Arrays.sort를 하면 위의 그림과 같은 모습입니다.

이제 dfs 함수를 시작하겠습니다.

처음 dfs를 실행하면 다음과 같은 그림이 됩니다.

before의 초깃값은 0이기 때문에 before != numArr[i] 조건을 통과하여 before을 초기화해줍니다.

cnt 즉 깊이가 2가 되어 M과 같아졌기 때문에 원래 재귀하여 다음 과정이 이렇게 나옵니다.

다음 과정에서 이제 변화가 생깁니다.

cnt의 값이 1일 때의 dfs가 9를 out[1]의 자리에 넣은 다음 출력 후 다시 돌아오면 cnt의 값이 1인 dfs의 before값은 9입니다.

이때 numArr[3]의 값은 before의 값과 같은 9입니다.

if(before != numArr[i])

따라서 위의 조건을 만족하지 못하여 이 중복된 결과에 대해서는 출력을 하지 않습니다.

따라서 다음의 진행은 다음의 그림과 같고 출력은 7 1이 됩니다.

이러한 과정을 반복하면 중복된 수열을 출력하지 않고 문제를 해결하실 수 있습니다.