Backtracking-N과 M (1)

www.acmicpc.net/step/34

백트래킹 단계

백트래킹이란?

 

-현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘-

 

-백트래킹은 재귀와 관련이 있다. (n-1개의 관한 것또한 일정한 패턴이 존재)

 

-DFS와 관계가 있다고 생각한다.(깊이우선탐색이 관련이 있는 이유는 해당 수를 계속적으로 재귀적으로 이어가다가 불충족시에는 다시 전단계 또는 전전단계 등... 되돌아오고 다음것으로 다음 안쪽으로 다음 안쪽에 안쪽으로... 불충족하면 돌아가고 충족하면 더 깊이 가다가 일정 조건을 만족한다면 충족이라고 간주 하는 것으로 보이기 때문이다.)

 

 

 

왜 재귀와 관련이 있을까?

 

예를 들어 설명하자면, 오목을 둘 때 기본적으로 상대방의 다음 수에 관한 경우의 수를 생각하는 것과 비슷하다.

오목의 룰은 대각선 또는 가로 그리고 세로로 5개의 오목알이 두면 이기는 것이다.

오목을 두기 시작하기 부터 내가 놓는 자리의 상대방의 다음 수(무한히 많다). 

이기기위한 전략으로 내가 놓는곳에 대한 상대방의 다음 수를 계속적으로 생각하다 보면 내가 여기에 두면 그 다음 상대방은 나를 방어하거나 또는 상대방의 공격으로 이어지는 수를 보고 전략을 짤 때 백트레킹을 이용한다.

 

결론적으로 백트래킹이란 내가 이길 수 있는 자리를 생각하며 경우의 수를 모두 따져보면서 아니면 다른 수를 생각하는 것이다. 

 

참조글:바킹독의 알고리즘.

blog.encrypted.gg/945

[실전 알고리즘] 0x0C강 - 백트래킹

 

N과 M (1)

 

 

해당 코드는 밑에 폴더를 다운로드.

 

 

// boj/15649
public class N_M {
// 4 3 4개중 3개 를 골라라.
static boolean visited[];
static int arr[];
static int m;
static int n;

public static void main(String[] args) {
n = 4; //1 부터 4 까지의 수들중.
m = 2; // 2개만 뽑아라.
arr = new int[m]; // 빈 arr , 여기에서는 해당 수들을 채워넣을 공간.
visited = new boolean[n + 1]; // 0번째는 쓰지 않음. (0번째 부터 해도 되지만 이게 편함.)
nM(0);
}

// cnt 는 현째까지 배열에 가지고 있는 수.
public static void nM(int cnt) //DFS
{
// 재귀 탈출 조건.
// 즉. 현재까지 선택한 숫자의 개수가 m의 개수와 일치하면 배열에 채워진 수들을 출력.
if (cnt == m) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}

for (int i = 1; i < n+1; i++) {
// visited 는 방문이 되었는지 안되어 있는지 체크하기 위한 것.
// visited를 사용하는 이유
// 만약 예를 들어 1이 먼서 선택된 후에 1이 선택이되는 중복은 제거하기 위해서.

if(!visited[i])
{
visited[i]=true;
arr[cnt]=i;
nM(cnt+1);
visited[i]=false;
}
}
}
}

 

 

 

 

 

N_M.java

0.00MB

코드 상단위에 package 제거!