* 핵심 개념

삼성 4월 역량테스트에 나왔던 문제다.

Backtracking으로 구현하면 되지만, 최적화를 하지 않으면 시간이 무지오래걸린다.

우선, 구현 순서에 대해 알아보면

1. 10*10 맵을 돌면서 1인지 확인한다.
2. 1이 있다면 5*5 색종이를 덮을 수 있는지 확인한다.
3. 색종이를 덮을 수 있다면 해당 맵을 0으로 바꾼다.
4. 색종이를 덮을 수 없다면 더 작은 색종이를 확인한다.

이런 방식으로 진행되는 Backtracking 방식이다.

하지만, 단순하게 조건만 따라 구현하면 시간 초과가 날 수밖에 없다.

이를 위해 다음과 같은 방법을 사용한다.

1. 매개변수로 row 값을 넘겨준다. 맵을 탐색할 때 row부터 시작하면 이전 줄은 확인하지 않아도 되므로 연산을 줄일 수 있다.    >> int r 파라미터로 사용
2. 입력 시에 1의 총 개수를 구하고 파라미터에 색종이로 지운 1의 개수를 계산하면서 넘긴다.        >> int total 파라미터로 사용
• 만약 지운 1의 개수와 입력받은 1의 개수가 같다면 ans에 최소값을 저장하고 return한다.
3. 큰 색종이부터 들어갈 수 있는지 확인해 보기 때문에, 큰 색종이로 덮을 수 있다면 작은 색종이는 확인해볼 필요 없이 가능하다. >> boolean flag 이용
• 1*1 색종이까지 확인했는데도 색종이를 넣을 수 없다면 함수를 return한다.
4. 해당 좌표를 바꾼 후에 아직도 1이 남아있으면 유효하지 않은 경우이므로 return한다.        >> 가지치기

가지치기 때문에 정말 고생이 많았던 문제다.

코드가 깔끔하지는 않지만 누군가에게 도움이 되길 바라며 공유한다.

* 문제

* 소스 코드

* 핵심

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

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

* 문제

* 소스 코드

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;
			}
		}
	}
}