[SWEA] 6871. 삼삼 트리플 게임

문제 정보

```

플랫폼	SWEA
문제	6781. 삼삼 트리플 게임
난이도	D3
언어	Java
문제 링크	문제 바로가기 →

```

카드는 숫자와 컬러로 구성되어 있다.

9장의 카드를 받으면 3개의 세트가 될 수 있는지를 구하는 문제이다.

 

하나의 세트(카드 3장)를 구성하는데 조건이 있다.

• 같은 카드 색이어야 한다.
• 숫자가 모두 같거나, 연속적이어야 한다.
  • 이때 9,1,2 같은 경우는 될 수 없다
• 숫자, 컬러가 같은 카드는 4장 이하로만 주어진다.

카드 
1 2 3 
R R R

 

이 경우는 1개의 세트가 된다. 

 

승리 조건을 만족하도록 3개의 세트를 구성할 수 있는지 판별해라..

2. 핵심 아이디어

카드에는 순서가 없다.
카드를 색깔별로 빈도로 수치화하고, 3장을 꺼내야 한다.

모든 경우를 파악해도 좋지만, 특정 컬러의 카드가 1, 2장만 있으면 세트를 만들 수 없다. 

주어진 9장의 카드에 대해서 순서를 유지할 필요가 없습니다.

원본 카드에 대해서 색깔별로 나누고, 각각의 색에 카드 숫자별 개수를 구한 후에, 조합하거나, 카드 한장이 1 이상인 경우 3개이거나, 연속적으로 존재하는지를 비교하며 풀어야 합니다.

3. 주의할 점

저는 재귀 + 백트레킹으로 문제를 풀었습니다. 

 

 해당 재귀 호출이 끝난 뒤 반드시 원래 상태로 복구해야 한다는 점을 주의해야 합니다. 그렇지 않으면 이후에 탐색하는 다른 경우의 수가 변경된 배열을 기준으로 탐색하게 되어, 현재 매개변수에 맞는 올바른 비교를 수행할 수 없습니다. 따라서 상태를 변경하고 탐색한 뒤에는 원상 복구하는 백트래킹 과정이 필수입니다.

4. 풀이 코드

public static void main(String[] args) {
        Map<Character,Integer> mapper = new HashMap<>();
        mapper.put('R',0); mapper.put('G',1); mapper.put('B',2);
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); sc.nextLine();

        for(int tc=1;tc<=n; tc++) {
            int[][] cache = new int[3][10];
            char[][] inputs = {sc.nextLine().toCharArray(), sc.nextLine().toCharArray()};

            for(int i = 0; i <9 ; i++) {
                int num = inputs[0][i] - '0';
                char col = inputs[1][i];
                cache[mapper.get(col)][num]++;
            }
            boolean res = dfs(cache[0]) && dfs(cache[1]) && dfs(cache[2]);
            System.out.printf("#%d %s\n", tc, res ? "Win" : "Continue" );
        }
    }
    static boolean dfs(int []seq) {
        int entry = 0;
        while( entry < 10 && seq[entry] == 0) { entry++; }
        if (entry==10) return true;
        if (seq[entry] >=3) {
            seq[entry]-=3;
            if(dfs(seq)) return true;
            seq[entry]+=3;
        }
        if (entry <= 7 && seq[entry] > 0 && seq[entry+1] >0 && seq[entry+2]>0) {
            seq[entry]--;
            seq[entry+1]--;
            seq[entry+2]--;
            if (dfs(seq)) return true;
        }
        return false;
    }
}

 

여기서 가능한 3개의 경우보다 하나라도 안되면 return false하는게 편한거 같습니다.

주의 할 점은 숫자가 8 or 9일 때 배열의 값이 1 이상일 때 그 부분도 처리해야합니다.

재귀 돌 때 총 2개의 경우에 대해 파악해야하기 때문에, 함수 실행시 매개변수의 데이터를 유지해야 합니다. 그래서 첫번째 if(dfs(seq)) return true; 이후에 seq를 다시 원 상태로 복귀(백트래킹) 해야 합니다.

6. 개선할 수 있는 부분

불필요한 반복, 자료구조, 객체 생성 등을 줄일 수 있는지 작성합니다.

• 더 단순한 자료구조를 사용할 수 있는가?
• 반복 횟수를 줄일 수 있는가?
• 문자열이나 배열을 불필요하게 생성하고 있지는 않은가?

7. 회고

어려웠던 점

```

처음에 문제 읽을 때 왜 108장의 카드가.. -> 중복해서 카드를 줄 수 있다는 의미였던거 같은데..

배운 점

재귀를 호출할 때 여러가지 경우를 파악해야할 경우 백트래킹 중요하다!어렵지 않다!

다음에 적용할 점

입력받은 배열의 원소가 순서를 유지 해야 하는가? 여부에 따라서 빈도수를 기준으로 배열을 재구성해도 좋겠다!

```