[Algorithm] 백준/5568 :: 카드 놓기

* 핵심

숫자를 보는게 아닌 각 입력값의 idx를 순서를 구분해서 뽑는 과정이다.

1234~1432, 2134~2431 ... 순서를 전부 확인하는 Backtracking 코드를 구현한다.

* 문제

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
public class Main {
	public static StringTokenizer stk;
	public static StringBuffer sb = new StringBuffer();
	public static HashSet<String> hs = new HashSet<>();
	public static boolean[] visited;
	public static String[] card;
	public static int cnt = 0, n, k;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		card = new String[n + 1];
		visited = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			card[i] = br.readLine();
		}
		dfs(k, 1, "");
		System.out.println(hs.size());
	}
	public static void dfs(int k, int idx, String s) {
		if (k == 0) {
			hs.add(s);
			return;
		}
		if (idx > n) {
			return;
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(k - 1, i, s + card[i]);
				visited[i] = false;
			}
		}
	}
}