백준 15649번: N과 M(1) (JAVA) <백트래킹 알고리즘>

 

문제 해석

 

N이 입력값으로 주어질 때 1부터 N까지의 수에서 중복없이 M개씩 골라 나올 수 있는 모든 경우를 구한다.

오름차순으로 출력해야 한다.

출력할 숫자들을 담을 배열이 필요할 것으로 보인다.

 

알고리즘

 

기준이 되는 숫자를 선택했을 때 나올 수 있는 경우를 모두 찾을 수 있어야 한다. 

N이 4이고 M이 2인 경우 기준이 되는 수가 1일 때 (1, 2) / (1, 3) / (1, 4) 가 출력되어야 하는데 일일이 증가시켜주며

인덱스를 변경해줄 수 없기 때문에 방문여부를 기록하고 재귀적으로 수행해야할 필요를 느꼈다.

 

백트래킹 알고리즘

 

이 방식은 백트래킹 알고리즘이다. 백트래킹 알고리즘은 브루트포스 알고리즘과 달리 모든 가능성을 다 뒤져보는 것이 아닌 가능성이 있는 경우만 찾는 알고리즘이다. 노드 방문 기록을 남겨 방문한 적이 있는 노드에 대해서는 관련 경우를 찾아보지 않도록 한다.

 

코드

depth는 트리의 깊이를 나타낸다.

 

순차적으로 숫자에 대한 visit(방문 기록)이 없는 상태(false)이면

방문한 것으로(true) 바꿔주고 result [depth]에 해당 숫자를 담는다. 

depth 가 m과 같아지면 기준에 대해 가능한 경우를 모두 result에 담은 것으로 배열에 들어있는 모든 요소를 출력한다.

재귀가 끝나고 해당 기준에 대한 결과가 출력이 되면 방문 기록이 사라지기 때문에

(1, 2, 3, 4) / (1, 2, 4, 3) 과 같은 경우 또한 출력이 가능하다.

 

N이 4이고 M이 4인 경우

resolve 함수의 반복문 부분 실행 순서를 보면

 

1차 호출: i=0 / visit[0]=true / result[0]=1 / resolve(1)

2차 호출: i=0 일 때 pass

i=1 / visit[1]=true / result[1]=2 / resolve(2)

3차 호출: i=0, 1 일 때 pass

i=2 / visit[2]=true / result[2]=3 / resolve(3)

4차 호출: i=0, 1, 2 일 때 pass

i=3 / visit[3]=true / result[3]=4 / resolve(4)

{1, 2, 3, 4} 출력 / resolve(4) 종료 / visit[3]=false / visit[2]=false

 

이 수행으로 4차 호출에서의 반복문이 종료되고 3차 호출의 resolve(3)도 종료되어 visit[2]=false가 된다.

이 후 다음 스텝인 i=3이 시작된다.

 

3차 호출: i=3 / visit[3]=true / result[2]=4 / resolve(3)

4차 호출: i=0, 1일 때 pass

i=2 / visit[2]=true / result[3]=3 / resolve(4)

{1, 2, 4, 3} 출력 / resolve(4) 종료 / visit[2]=false / visit[3]=false / visit[1]=false