백트래킹

[BOJ_4574] 스도미노쿠 (java)

문제링크 https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 재귀, 브루트포스, 백트래킹 스도미노쿠는 스도쿠 + 도미노를 의미하는 게임이다. 스도쿠의 규칙을 지켜주며, 도미노(2개의 쌍으로 이루어진 값)을 놓아주어 스도쿠를 풀어주는 문제이다. 도미노는 $(1,2), (1,3) (1,4) ... (7,8) (7,9) (8,9)$ 까지 1부터 9까지의 모든 값의 쌍으로 이루어져 있다. 그런데 $(1..

브루트포스(2) 재귀

재귀를 쓰면 재귀를 쓰면 모든 경우의 수를 확인하도록 만들 수 있다. 재귀를 써서 모든 경우를 확인하는 경우는 두가지이다. 1. 순서가 있는 경우(P) n개의 수를 나열하는 방법의 수이다.(중복가능) -> O(n!) /** * index -> 현재 수를 놓는 위치 * arr -> 확인하려고 만드는 배열 */ public void recursive1(int index, int[] arr){ if(index == arr.length){ //종료 조건 } for(int i = 1; i O(2^n) /** * index -> 현재 수를 놓는 위치 * arr -> 확인하려고 만드는 배열 */ public void recursive2(int cnt, int[] arr, int value, int n){ if(ind..