[JAVA]백준 5568번 카드 놓기

📌문제 링크

---

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

📌문제 설명

---

입력 범위가 작아서 일반 브루트포스로도 해결 가능합니다. 백트래킹 or 브루트포스로 완전탐색을 진행한 후 HashSet에 결과값을 넣고 HashSet의 size를 출력하면 됩니다.

📌코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, K;
    static ArrayList<String> list = new ArrayList<>();
    static Boolean[] visited = new Boolean[100];
    static HashSet<String> set = new HashSet<>();

    public static void main(String[] args) throws Exception {
        input(); // 입력을 받는 메서드 호출
        solve(); // 문제를 해결하는 메서드 호출
    }

    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine()); // 첫 번째 입력값을 N으로 설정
        K = Integer.parseInt(br.readLine()); // 두 번째 입력값을 K로 설정
        for(int i = 0; i < N; i++) {
            String num = br.readLine(); // 각 줄의 입력값을 num으로 설정
            list.add(num); // 리스트에 num 추가
        }
        for(int i = 0; i < N; i++) {
            visited[i] = false; // 방문 배열 초기화
        }
        br.close(); // BufferedReader 닫기
    }

    public static void backTracking(int idx, int cnt, String str) {
        if(cnt == K) { // K개의 숫자를 선택했을 때
            set.add(str); // 집합에 문자열 추가
            return;
        }
        for(int i = 0; i < N; i++) {
            if(visited[i]) continue; // 이미 방문한 경우 건너뛰기
            visited[i] = true; // 방문 표시
            backTracking(i, cnt + 1, str + list.get(i)); // 재귀 호출
            visited[i] = false; // 방문 표시 해제
        }
    }

    public static void solve() {
        backTracking(0, 0, ""); // 백트래킹 시작
        System.out.println(set.size()); // 결과 출력
    }
}