BackTracking

Permutation

Permutation : 순열 -> 순서가 존재
표기 : nPr
ex) 1,2,3이 있을 때 중복없이 나올 수 있는 순열의 수
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] -> 총 6가지

Combination

Combination : 조합 -> 순서가 없음
표기 : nCr
ex) 1,2,3이 있을 때 조합의 수
[1,2,3] -> 1가지

DFS, BFS, BackTracking 차이

1. BFS는 큐를 이용하여 인접한 것부터 하나씩 찾는 알고리즘
2. DFS는 스택을 이용하여 깊이있게 하나씩 찾는 알고리즘
3. BackTracking은 DFS와 유사하게 스택을 이용하지만, 불필요한 부분은 탐색하지 않고 이전 단계로 돌아가서 다른 해를 찾는다.

문제

1. Permutation

Input : nums = [1,2,3]
Output : [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

풀이

1. 재귀를 이용해서 풀어야 함으로 탈출 조건을 잘 파악해야한다.
   -> tempList.size() == nums.length
2. 그 외에는 nums[] 에서 하나씩 빼서 tempList에 넣는다.
3. backtraking()을 재귀적으로 호출한다.
4. 탈출하면 다시 tempList에서 하나를 뺀고 다시 수를 넣는다.
5. 중복허용이 안되기 때문에 다음과 같은 조건을 넣는다.
   -> if(tempList.contains(nums[i])) continue;

tempList 에 담기는 과정 -> 중복을 거르지 않았을 때
[],
[1],
[1, 1],
[1, 1, 1],
[1, 1, 2],
[1, 1, 3],
[1, 1],
[1],
[1,2],
[1,2,1],
[1,2,2],
[1,2,3],
[1,2],
[1],
...

경우의 수 -> 진한 부분이 최종적으로 뽑아야 하는 부분
[1, 1, 1], [1, 1, 2], [1, 1, 3],
[1, 2, 1], [1, 2, 2], [1, 2, 3],
[1, 3, 1], [1, 3, 2], [1, 3, 3],
[2, 1, 1], [2, 1, 2], [2, 1, 3],
[2, 2, 1], [2, 2, 2], [2, 2, 3],
[2, 3, 1], [2, 3, 2], [2, 3, 3],
[3, 1, 1], [3, 1, 2], [3, 1, 3],
[3, 2, 1], [3, 2, 2], [3, 2, 3],
[3, 3, 1], [3, 3, 2], [3, 3, 3]

소스

import java.util.*;

public class Q1 {

	public static void main(String[] args) {
		int[] nums = { 1, 2, 3 };
		System.out.println(solve(nums));
	}

	public static List<List<Integer>> solve(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> tempList = new ArrayList<Integer>();

		backtracking(result, tempList, nums);

		return result;
	}

	public static void backtracking(List<List<Integer>> result, List<Integer> tempList, int[] nums) {

		if (tempList.size() == nums.length) {
			result.add(new ArrayList<>(tempList));
		} else {
			for (int i = 0; i < nums.length; i++) {
				if (tempList.contains(nums[i])) {
					continue;
				}
				tempList.add(nums[i]);
				backtracking(result, tempList, nums);
				tempList.remove(tempList.size() - 1);
			}
		}
	}

}

2. Combination

N이 주어졌을 때 1~N까지의 수를 이용하여 k개 만큼의 조합을 구해라.
Input: n = 3, k = 2
Output: [[1, 2], [1, 3], [2, 3]]

풀이

1. 재귀를 이용해서 풀어야 함으로 탈출 조건을 잘 파악해야한다.
   -> tempList.size() == k : result.add(tempList)
   -> tempList.size() > k : return;
2. 그 외에는 for문을 start부터 N까지 돌린다.
3. 이때 tempList에 하나씩 넣으면서 backtracking() 호출한다.
4. backtracking()을 호출할 때 start 부분에는 i+1를 넣어 중복을 방지한다.
5. 만일 중복을 허용할 것이라면 start를 넣으면 된다.
6. 호출한 뒤에는 tempList.remove(tempList.size() -1) 를 해주어 하나씩 빼면서 다시 for문을 돌린다.

소스

import java.util.*;

public class Q2 {

	public static void main(String[] args) {
		int n = 3, k = 2;
		System.out.println(solve(n, k));

	}

	public static List<List<Integer>> solve(int n, int k) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> tempList = new ArrayList<Integer>();

		backtraking(result, tempList, n, k, 1);

		return result;

	}

	public static void backtraking(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {

		if (tempList.size() == k) {
			result.add(new ArrayList<>(tempList));
		} else if (tempList.size() > k) {
			return;
		}

		for (int i = start; i <= n; i++) {
			tempList.add(i);
			backtraking(result, tempList, n, k, i + 1);
			tempList.remove(tempList.size() - 1);
		}
	}

}

참고

인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디