[LeetCode] Beautiful Arrangement 자바

문제

 

https://leetcode.com/problems/beautiful-arrangement/description/

 

▫️ 1~n까지 라벨링된 정수 n개가 있다고 가정하자

▫️ 모든 i에 대해서 아래 조건이 하나라도 참인 n개의 순열은 Beautiful Arrangement이다

    - perm[i]는 i로 나뉘거나

    - i는 perm[i]로 나뉘거나

▫️n이 주어질때, 만들 수 있는 beautiful arrangements 개수를 리턴하라

 

 

문제 풀이

 

이 문제를 포스팅해야겠다고 생각이 든 이유는 나름 참신한 DFS라고 느꼈기 때문이다.

보통 순열을 만들때 사용되는 정수 배열을 arr이라 하면 방문 배열 또한 arr[i]의 사용 여부에 따라 인덱스가 visited[i]로 똑같이 따라가는데, 해당 문제는 visited배열과 실제 배열의 인덱스 값이 별도로 쓰여진다.

 

✅ 알고리즘

1. DFS함수를 이용해 1~n까지의 수로 이루어진 순열 배열 perm을 생성한다.

2. 1~n까지의 수를 perm에 넣으면서 Beautiful Arrangement에 해당하는지의 조건을 바로 바로 확인한다.

3. 만약 조건이 되는 경우 DFS 재귀함수를 또 호출하면서 depth를 증가시켜간다.

   - visited[i] : i 숫자가 사용되었는지 여부

   - depth : perm배열의 인덱스

4. 조건이 안되는 경우 되는 숫자를 찾을때까지 for문이 돈다.

 

→ 모든 경우의 완전탐색하면서도 특정 조건에 맞는 경우만 확인하기에 백트래킹이라고 볼 수 있을 것 같다

💡 백트래킹? 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것

 

 

소스 코드

 

static answer;
static boolen[] visited;

public static int countArrangement(int n) {
	answer = 0;
	visited = new boolean[n+1];
	DFS(n, 1, new int[n+1]);
	return answer;
}
	
public static void DFS(int n, int depth, int[] perm) {
	if(depth == n+1) {
		answer++;
		return;
	}
	
	for(int i = 1; i <= n; i++) {
		if(!visited[i]) {
			if(i % depth == 0 || depth % i == 0) {
				perm[depth] = i;
				visited[i] = true;
				DFS(n, depth+1, perm);
				visited[i] = false;
			}
		}
	}
}