[백준 알고리즘 5568] 카드 놓기 - Java [브루트포스 , DFS]

 5568번: 카드 놓기 (acmicpc.net)

5568번: 카드 놓기

 

 

 

 

 

 

[해설 및 풀이]

 

이 문제의 경우는 깊이 우선탐색인 dfs로 푸는것이 좋은 문제입니다.

 

자 문제를 뜯어보자면

 

 

 

이 부분을 읽어본다면 즉

 

4개의 카드를 놓고

 

2개의 카드를 조합한다 합니다.

그렇게 된다면 첫번째 카드를 뽑는다면 1이 되겟죠.

 

그 1를 하나하나 다 조합 해봅니다.

 

12

112

11

 

1의 경우 3개의 조합이 나옵니다.

 

그 후 2를 뽑습니다.

 

그러면

 

21

212

21 (중복)

 

21

212

 

즉 이런식으로 총 조합을 만들어 구한다고 합니다.

 

그렇게 된다면 잘 생각해봐야 합니다.

 

즉 카드가 2개 일때 조합이 완성되기 때문에 카드가 2개 일때는 이 조합카드를 넣어야 합니다.

 

하지만 이 문제의 겨우 2개의 조합을 뽑는 조건이 아닌 m개의 조합을 뽑아라고 하기때문에

m개의 조합이 변칙적으로 작용합니다.

그렇기 때문에 반복문으로는 찾을 수 없습니다.

 

그렇기 때문에 재귀함수를써야합니다.

m개의 조합이 생겼을때 재귀함수를 사용해서 변칙적인 값들을 찾을 수 있습니다.

 

블랙잭 문제를 생각하면 쉽습니다.

블랙잭의 경우 1개의 값들을 3번 뽑아서 숫자를 조합하는 하기 때문에

3중 반복문으로 돌리면 되지만

 

이 문제의 경우 2개의 값들을 뽑아서 모든 조합을 찾아야 하기 때문에

 

1개의 값들을 3개를 뽑으라 한다면 3중 반복문으로 사용하면 되지만

 

2개이상의 값들을 뽑아서 조합을 하라한다면 무조건 dfs라고 생각하면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int card;
    static int combination;
    static boolean[] setNum;
    static int[] card_array;
    static Set<String> set = new LinkedHashSet<>();
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
        card = Integer.parseInt(st.nextToken()); //총 놓을 카드 수

        st = new StringTokenizer(br.readLine());

        combination = Integer.parseInt(st.nextToken()); // 조합 개수

        card_array = new int[card]; //카드를 저장할 배열
        setNum = new boolean[card]; //무슨 카드가 뽑혔는지 확인하는 배열
        
        for(int i=0; i<card;i++){
            st = new StringTokenizer(br.readLine());
            card_array[i] = Integer.parseInt(st.nextToken());
        }

            Recursive("",0);

        System.out.println(set.size());
      }

      public static void Recursive(String str,int count){

        if(count == combination) {
            set.add(str);
            return;
        }

        for(int i=0; i<card;i++){

            if(!setNum[i]){ // 배열이 fasle면 즉 = 카드가 안뽑혔으면
                setNum[i] = true; // 하나의 카드를 뽑고 재귀로 들어감
                Recursive(str + card_array[i],count + 1);
                setNum[i] = false; // 재귀가 끝나면 다시 카드 원상태로 
            }
        }
      }
    }

 

 

 

 

자 하나하나 살펴봅시다.

 

for(int i=0; i<card;i++){

    if(!setNum[i]){ // 배열이 fasle면 즉 = 카드가 안뽑혔으면
        setNum[i] = true; // 하나의 카드를 뽑고 재귀로 들어감
        Recursive(str + card_array[i],count + 1);
        setNum[i] = false; // 재귀가 끝나면 다시 카드 원상태로
    }
}

 

이 부분이 가장 햇갈릴텐데

 

재귀함수를 안다는 가정하에 설명하겠습니다.

 

일단 이 메서드는 반복문인 for = 4 까지 가지고있습니다.

 

즉 그렇게 된다면 이 재귀함수로 들어가면 

 

그 다음 재귀함수도 메서드에 반복문이 for = 4까지 반복됩니다.

 

즉 쉽게 생각한다면

 

1  -> [11,112,12] 4번 반복

 

2-> [21,212,21] 4번 반복

 

12->[112,212,112] 4번 반복..

 

이런식으로 재귀함수 메서드안엔 반복문이 for 4이기 때문에 이렇게 모든 조합마다 반복이 가능합니다.

 

아직까지 이해가 힘들텐데 그림으로 본다면

 

(그림을 잘못 그렸는데 re("",0) i = 0에 [F,F,F,F]가 아니라 [T,F,F,F]입니다..

 

 

 

처음으로 recursive 메서드에 들어가면 매개변수는 (" " ,  0 )입니다.

 

if(count == combination) {
    set.add(str);
    return;
}

 

여기서는 count = 0 임으로 false

 

처음에 들어가면 당연히 boolean 배열은 [F,F,F,F] 입니다 이것은 카드를 뽑지 않았다는 뜻이죠.

 

if(!setNum[i]){ // 배열이 fasle면 즉 = 카드가 안뽑혔으면
    setNum[i] = true; // 하나의 카드를 뽑고 재귀로 들어감

 

그 후 False면 if문에 진입 후

첫번째 카드를 트루로 바꿔 줍니다.

그 후 재귀함수로 진입

 

 

 

 

그렇다면 re에 들어간 메서드는 1과 count = 1인 상태로 들어갑니다.

 

if(!setNum[i]){ // 배열이 fasle면 즉 = 카드가 안뽑혔으면
    setNum[i] = true; // 하나의 카드를 뽑고 재귀로 들어감

 

그 후 if문을 확인 해보지만 저희는 카드를 한장 뽑았기에 

불린 배열 값은 [TRUE,FALSE,FALSE,FALSE]로 되어있습니다.

 

그렇기 때문에 if문은 false 임으로 i = 1증가.

 

불린배열 인덱스 1값을 확인 하니 false임으로 true로 바꿉니다.

 

그렇다면 불린 배열은 [TRUE,TRUE,FALSE,FALSE]인 상태죠.

 

그 후 재귀로 진입

 

 

현재 스택에 쌓인 메서드는 총 3개입니다.

 

그후 다시 들어가니 String 값은 12 , count = 2입니다.

 

if(count == combination) {
    set.add(str);
    return;
}

 

하지만 다음 재귀로 들어가니 count == 2 리스트에 값을 추가하고 함수를 종료하는 명령문이 있죠.

 

그렇기 때문에 값을 추가하고 이 메서드는 종료

 

setNum[i] = false; // 재귀가 끝나면 다시 카드 원상태로

 

그후 재귀가 종료되면 이 불린 배열의 값을 false로 바꿈.

 

그 후 다시 반복문을 돕니다.

 

그 반복문을 돌면 i=2가 되죠?

 

 

자 그러면 원래는 True , True , False , False 였지만 이제는

 

T,F,T,F로 바뀌었습니다.

 

지금 re(1,1)의 메서드는 종료되지 않았습니다.

이 메서드는 i = 4번 돌때까지 절대 종료되지 않습니다. 그 이유는 이 메서드

count = 2가 될일이 없는 메서드 이기때문에 반드시 4번을 다 돌아야 합니다.

 

즉 이 메서드는 count = 1를 가지고 있습니다.

 

그 후 다시 재귀 진입.

 

그 재귀값은 112 , count = 2임으로 값 추가.

그 후 리턴

 

setNum[i] = false; // 재귀가 끝나면 다시 카드 원상태로

 

재귀가 끝낫음으로 밑에 코드가 실행되고 이 True였던 배열은 false로 바뀝니다.

 

그 후 다시 반복문을 도니 i = 3입니다.

 

 

즉 이렇게 다시 들어가겠죠.

 

그렇다면 re(1,1)의 메서드는 제가 위에서 말했다 싶이 count는 영원히 1임으로

 

반복문이 4번끝날때 까지 절대 종료되지 않습니다.

하지만 i = 3이 됨으로써 이 re(1,1)의 메서드는 종료가 되었습니다.

 

 

 

 

그렇다면 이 re(1,1)메서드는 끝낫기 때문에 재귀 함수 종료.

 

 

드디어 첫번째 재귀함수가 끝났습니다.

맨처음에 re("",0)이었던 메서드에서 재귀함수로 계속 들어가서 드디어 끝이난겁니다.

 

그러면 re("",0)의 i는 무엇이었죠? 이 메서드는 이 재귀에서 계속 멈춰있었고 반복문을 단 한번도 돌지 않았습니다.

그렇기 때문에 i = 0 이됩니다.

그렇기때문에 불린 배열 0번째를 false

 

그렇다면 불린 배열은 [False,False,False,False]가 됩니다.

 

그 후다시 i = 1이되며 위에와 같은 과정이 반복되며

 

값들을 찾아옵니다.

 

 

즉 dfs란 결국 m개의 조합 = 변칙적인 조합을 찾을 때 사용하는 알고리즘이며

 

이 문제는 count = 2 즉 조합이 n개 일때 값들을 찾으라고 하였음으로

 

count로 깊이 탐색을 진행한 문제입니다.