백준사이트의 N과 M문제를 통해 백트래킹을 이해해봅시다
백트래킹에 대해 먼저 검색해보면 정답이 아니라고 판단되는 경우, 다른 정답을 찾는 방법 정도로 검색이 되는데요
문제를 보면서 제가 생각했던 접근법과 풀이를 적으며 백트래킹을 더 깊게 이해해봅시다
1번 문제
1번 문제는 1 ~ N까지의 숫자들 중 M개를 뽑아서 중복 없이 수열을 만듭니다
그 수열을 중복 없이, 공백 구분해서, 사전순으로 출력합니다
사전순은 미리 정렬해놓으면 쉽게 가능합니다
접근법
첫 접근은 예제만 보고 2중 for문 구조를 생각했습니다
하지만 다시 생각해보니 3개를 뽑는다면 3중 for문, 4개를 뽑는다면 4중 for문...
for문을 리터럴하게 하는 방식은 아니라고 생각했고, 재귀를 이용하게 되었습니다
카드를 m중 반복으로 뽑아야 하고, 이미 뽑은 수는 뽑을 수 없기 때문에 뽑은 수에 대한 기록이 필요합니다
뽑은 수를 배열에 저장해서 재귀에 계속 넘기면 되겠군요
function solution(n, m) {
const set = new Set();
for (let i = 1; i <= n; i++) {
dfs([]);
}
return [...set].join("\n");
function dfs(temp) {
if (temp.length === m) {
set.add(temp.join(" "));
return;
}
for (let i2 = 1; i2 <= n; i2++) {
if (temp.includes(i2)) continue;
temp.push(i2);
dfs(temp);
temp.pop();
}
}
}m중 반복이 완료될때까지 숫자를 뽑습니다
이 문제에서 정답이 아니라고 판단되는 경우는 이미 뽑은 수를 뽑는 경우 입니다
따라서 그 경우를 건너뛰도록 합니다
응용 문제들
2번 문제
2번 문제는 조건이 추가되었는데요
고른 수열이 오름차순이어야 합니다
2 1, 3 1 과 같은 수열은 해당하지 않습니다
다르게 말하면 이미 고른수보다 큰 수를 고르라는 말과 같습니다
이 문제에서 정답이 아니라고 판단되는 경우는 이미 뽑은 수를 뽑는 경우와 이미 뽑은수보다 작거나 같은 수를 뽑은 경우 입니다
해당하는 경우를 건너뛰도록 해도 되지만, 뽑은 수 index 다음부터 확인하면 됩니다
index 1을 뽑았다면, index 0은 무조건 볼 필요가 없습니다
// index는 뽑은 수의 index
for (let i = index; i <= n; i++) {
temp.push(i);
dfs(i + 1, temp);
temp.pop();
}3번 문제
3번 문제는 같은 수를 여러번 골라도 된다는 조건이 추가되었습니다
이 경우 정답이 아니라고 판단되는 경우가 없습니다
따라서 계속 1부터 n까지 뽑도록 합니다
for (let i2 = 1; i2 <= n; i2++) {
temp.push(i2);
dfs(temp);
temp.pop();
}4번 문제
4번 문제는 비내림차순이어야 한다는 조건이 추가되었습니다
오름차순의 경우 이미 뽑은 수보다 작은 수를 뽑지 않아야 했는데, 이 경우는 같은 수를 뽑아도 됩니다
따라서 정답이 아니라고 판단되는 경우는 이미 뽑은수보다 작은 수를 뽑은 경우 입니다
index가 작은걸 뽑으려고 하면 건너뛰도록 해도 되지만, 뽑은 index부터 돌리면 그 경우를 제외하는것과 같습니다
for (let i = number; i <= n; i++) {
temp.push(i);
dfs(i);
temp.pop();
}이후 응용 문제들은 index 접근 정도의 차이가 있지만 조건 한두개 차이로 비슷한 문제입니다
백트래킹 문제의 핵심은 존재하는 경우들 중 정답이 아니라고 판단되는 경우를 패스해야 합니다
문제를 잘 읽고 요구사항을 분석해서 요구사항에 어긋나는 경우, 정답이 아니라고 판단되는 경우를 알아야 합니다
정리
백트래킹은 존재할 수 있는 경우 중 정답이 아니라고 판단되는 경우에 대해 건너뛰거나 계산을 중지시키고
다른 경우를 계산해야 합니다
참고
