[C++] 백준 15649번 N과 M (1)

백트래킹의 기본적인 문제.

백트래킹 알고리즘을 알고있다면 쉽게 접근할 수 있는 문제이다.

 

백트래킹이란?

기본적으로 백트래킹은 '가능한 모든 방법을 탐색'한다는 데 그 기본 아이디어가 있습니다. 이 아이디어의 구현은 DFS, BFS 둘 다 가능한 방법입니다. 다만, 백트래킹은 보통 '불가능한 방법'임을 인지한다면 이전 상태로 돌아오는 작업이 필요한데 이는 큐를 사용하는 BFS보다는 스택(혹은 재귀)을 사용하는 DFS가 더 편하기 때문에 일반적으론 DFS를 사용합니다. 출처 : https://www.acmicpc.net/board/view/15738 - simm4256님 댓글 참고

쉽게 말해서 내가 길을 가다가 이 길이 아닌거 같으면 돌아가서 다른 길로 가는 것을 뜻한다.

물론 경우의 수가 상당히 많으로 시간복잡도 고려를 잘 해야 한다. 입력받는 N이 크다면 백트래킹으로 접근하는 것은 거의 불가능하다.(가지치기를 상당히 잘 해야 한다.)

 

 

따로 설명할 것 없이 바로 코드 리뷰를 하겠다.

사용한 STL과 변수

우선 vector STL을 사용했다.

수열에 수를 담을 vector v를 정의했고

n과 m은 문제에 나온 변수이고,

이미 내가 이 수를 vector에 담았는지 체크하는 check 부울 배열도 만들었다.

 

백트래킹 메서드

백트래킹을 구현한 메서드이다. 재귀를 사용해서 구현했고

내가 지금 M번째까지 입력을 모두 받았다면 벡터에 담겨있는 모든 수를 출력하도록 만들었다.

(시작할 때 처음 수를 넣고 idx를 1로 넣었기 때문에 idx는 사실 담겨 있는 수라고 생각하면 된다.)

M번째까지 입력받지 않았다면 반복문으로 내가 지금 보고 있는 수가 벡터에 담겨있는지 check 배열로 확인한다.

담겨있지 않다면 수를 담고 check 배열에 해당 수 번째에 해당하는 곳을 true로 바꾼다. 다시 find 메서드를 호출한다.

후에 메서드 호출이 끝나면 check 배열을 다시 false로 바꾸고 vector에서 해당 수를 pop한다.

 

메인함수

메인메서드에서는 그냥 첫번째 수가 무엇인지만 정하고 백트래킹과 같다.

 

백트래킹을 알면 어렵지 않게 풀 수 있다.

 

kimyunseok/study-record

코드는 위에서 확인할 수 있다.