https://www.acmicpc.net/problem/15649
문제
> 자연수 N과 M이 주어졌을때 1부터 N까지의 자연수 중 중복없이 M개를 고른 수열을 모두 구해라.접근
백트래킹을 사용해 문제를 해결한다. 재귀함수를 통해 백트래킹을 구현해 모든 경우를 돌며 해답을 찾으면 종료한다.
백트래킹
> 해답을 찾아가는 모든 경우를 시도하다가, 불가능하다고 판단되면 바로 돌아와서(백트랙) 다른 길을 찾는 방법이다.
> 백트래킹의 특징은
1. 가능한 모든 선택지를 시도한다.
2. 불가능한 경로는 빨리 포기(가지치기)한다.
3. 시도하며 상태를 바꿔가다 함수를 다시 호출한다.(재귀)
4. 해답을 찾으면 바로 종료.(쓸데없는 연산 안함)
> 대표적인 백트래킹 문제는
1. N-Queens 문제
NxN체스판에 퀸 N개를 놓되, 서로 공격하지 못하게 배치
2. 미로탈출, 탐색 문제
3. 특정 규칙을 가진 문자열, 수열 찾기문제
등에 사용된다.문제해결
> 일단 M을 3이라고 생각하고 적어보겠다.
> 함수 Backtracking()을 선언한다. M개로 이루어진 수열을 출력하기 때문에 먼저 결과 벡터 result의 크기가 3인지검증해 맞으면 출력한다. 재귀함수로 구현하기 때문에 return을 통해 빠져나갈 곳을 만든다.
> 1부터 입력받은 N까지 i가 방문하지 않은 수면 해당 i를 result에 넣고 함수를 다시 호출한다. 수열의 다음 수를 탐색하기 위해서이다.
> 다시 호출된 함수로 두번째 자리를 찾는다. 앞에서 i인 1은 visited가 true이므로 2부터 탐색한다. 2일 때 result에 들어가고 다시 함수를 호출한다. 현재 result는 {1, 2, }이다.
> 마지막 자리를 탐색하며 1, 2는 true상태이므로 3부터 들어온다. 3이 들어오고 다시호출된 함수에서 result가 {1,2,3}으로 크기가 3이기 때문에 출력문을 실행하고 return으로 함수를 깨고나온다.
> 함수가 깨져 재귀함수 밑에 두 문장이 실행된다. i가 3이었으므로 3이 false로 다시 미방문 상태가 되고 result벡터의 마지막 인덱스를 지운다. result는 {1,2, }상태이다.
> i가 이제 4이며 4가 들어온뒤 result가 {1,2,4}가 되어 앞선 3처럼 M과 크기비교하는 조건에 걸려 1,2,4가 출력되고 i가 5로 넘어간다.
> 5까지 끝난 후 수열의 3번자리에 대한 Backtracking()함수가 끝난다. 그래서 3번자리를 하기 전 2번자리의 i가 2였으므로 visited[2]가 false가 되고 result는 {1, , }상태가 된다.
> 2였던 i가 3이되고 result는 {1, 3, }인 채로 3번자리를 탐색한다. 이 과정이 반복 되어 1번자리의 i가 N에 도달할 때까지 탐색한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<bool>visited;
vector<int> result;
void Backtracking()
{
if (result.size() == M)
{
for (auto i : result)
cout << i << " ";
cout << '\n';
return;
}
for (int i = 1; i <= N; i++)
{
if (!visited[i]) // 아직방문안함
{
visited[i] = true;
result.push_back(i);
Backtracking();
visited[i] = false;
result.pop_back();
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
visited.assign(N + 1, false);
Backtracking();
}
후기
재귀를 잘 다뤄본적이 없어서 처음에 stack으로 해보려다 반복문만 4,5개 쓰고 예외는 예외대로나오고 매우복잡해서 논리적 오류도 생겼다.
재귀가 훨씬 쉽고 적합하다고하여 재귀로 구현했다. 재귀의 동작방식을 이해하는데 어렵긴 했지만 잘 따라가면 쉽고 편한 방식이다.
