해당 포스팅은 백준 문제인 N과 M(1) 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 DFS와 백트래킹으로 풀이하였다.
🤯 풀이
바킹독님의 풀이를 보고 풀었다.
드디어 첫 백트래킹 풀이다! 백트래킹 이론만 알았지 언제 써야할지 어렵길래 안 썼는데 저렇게 조합이나 수열 구할 때 쓰이는구나 🤔
해당 문제는 자연수 N과 M이 주어질 때 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제다. 백트래킹을 이용해 비어있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 M인 수열이 완성되면 출력 후 이전 depth로 돌아가는 식으로 구현하면 된다.
💡 로직 설명 - 백트래킹을 이용
맨 처음에는 빈 리스트로 시작하자. 이 리스트에는 dfs를 이용해 수열을 저장할 것이다.
리스트의 첫 번째 원소를 1로 둔다. 여기서 별은 현재 위치를 의미한다.
두 번째 원소로 2를 둔다.
마지막 원소로 3을 둔다. 이제 모든 칸이 찼으므로 수열을 완성(1 2 3)한 것이니 출력하고, 그 다음 수열을 구하기 위해 이전 상태로 돌아간다.
현재 위치에서 3번째 원소로 3와 4가 가능한 상태이다. 3은 이미 쓰였으니 4를 넣은 상태로 이동한다.
이제 모든 칸이 찼으니 수열(1 2 4)을 완성한 것이니 출력하고 다음 수열을 구하기 위해 이전 상태로 돌아간다.
현재 위치에서 3번째 원소로 3과 4가 가능한 상태다. 하지만 3과 4는 이미 다 쓰였으므로 더 이상 현재 상태에서 수열을 만들 수 없다. 따라서 이전 위치로 돌아간다.
현재 위치에서 2번째 원소로 2,3,4가 가능한 상태다. 2는 이미 쓰였으니 3을 넣은 상태로 이동한다.
현재 아직 사용하지 않은 수는 2와 4이니 먼저 3번째 칸에 2를 넣어보고 되돌아와 4를 넣으면 된다.
그러면 아래와 같은 수열이 만들어진다.
해당 과정을 반복하면 1부터 4까지 자연수 중에서 중복 없이 3개를 고른 수열을 모두 구할 수 있다.
👀 구현 방법 + 코드
seq: 수열 상태를 저장할 배열. 처음에는 아무 숫자도 들어가지 않으므로(수열 생성x) 각 원소를 0으로 초기화한다.visited= 1부터 N까지의 숫자 중 쓰일 수 있는 숫자와 없는 숫자를 체크해주는 배열. 처음에는 아무 숫자도 쓰이지 않았으므로 각 원소를 false로 초기화해준다.
const seq = [...Array(m)].fill(0);
const visited = [...Array(n)].fill(false);result: 모든 수열의 조합을 저장할 문자열. 처음에는 아직 만들어진 수열이 없으므로 빈 문자열로 초기화한다.
let result = "";dfs(0): 수열을 구하기 위해 dfs 호출. dfs의 인자는 현재 수열의 원소 개수를 의미하며 인자가 m과 같아질 때(수열 완성) 현재 수열을 출력한다.
dfs(0)-
dfs 함수 안의 for문: for loop를 n만큼 돌리면서 현재 방문하지 않은 원소가 있는지 판별한다. 방문하지 않은 원소가 있다면 해당 원소를 방문표시 한 다음 dfs를 돌린다. dfs 종료 후(k === m) 다시 현재 상태로 돌아왔을 때(백트래킹) 현재 원소를 false 처리한다(해당 원소가 쓰이지 않은 이전 상태로 돌아왔으니 방문표시를 제거해야 한다). -
dfs 함수 안의 if문: 만약 k === m일 시 수열이 완성된 것이므로 수열을 저장한 seq 원소를 문자열 result에 더한다.
function dfs(k) {
if (k === m) {
const arr = [];
for (let i=0; i<m; i++) {
arr.push(seq[i]);
}
return result += `${arr.join(' ')}\n`;
}
for (let i=1; i<=n; i++) {
if (!visited[i]) {
seq[k] = i;
visited[i] = true;
dfs(k+1);
visited[i] = false;
}
}
}🔥 전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0,-1);
const NM = input[0].split(" ");
const [n,m] = NM.map(el => Number(el));
function solution(n,m) {
const seq = [...Array(m)].fill(0);
const visited = [...Array(n)].fill(false);
let result = "";
function dfs(k) {
if (k === m) {
const arr = [];
for (let i=0; i<m; i++) {
arr.push(seq[i]);
}
return result += `${arr.join(' ')}\n`;
}
for (let i=1; i<=n; i++) {
if (!visited[i]) {
seq[k] = i;
visited[i] = true;
dfs(k+1);
visited[i] = false;
}
}
}
dfs(0);
return result;
}
console.log(solution(n,m));(ref) 바킹독님의 풀이
