[백준 node.js / javascript] N과 M1(15649) 문제

문제 :

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력 :

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력 :

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

코드 :

const fs = require("fs");
const [N, M] = fs
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split(" ")
	.map((v) => Number(v));
let arr = Array.from({ length: M }, () => 0);
let visited = Array.from({ length: N }, () => 0);

function backtrack(depth) {
	if (depth === M) {
		console.log(arr.join(" "));
	} else {
		for (let i = 1; i <= N; i++) {
			if (visited[i - 1] === 0) {
				arr[depth] = i;
				visited[i - 1] = 1;
				backtrack(depth + 1);
				visited[i - 1] = 0;
			}
		}
	}
}

backtrack(0);

 

코드 설명 :

 

1부터 N까지의 숫자 중에서 중복 없이 M개를 선택하여 수열을 만드는 문제를 해결하기 위해 백트래킹 알고리즘을 사용했습니다. 백트래킹은 가능한 모든 조합을 시도해 보지만, 그 과정에서 조건에 맞지 않는 경우는 조기에 탐색을 중단하고 다른 경로를 탐색합니다.

 

먼저, 중복을 피하기 위해 visited 배열을 준비합니다.

let visited = Array.from({length : N}, () => 0);

 

이 배열은 모든 요소를 0으로 초기화하여, 각 숫자가 수열에 이미 포함되었는지 여부를 추적합니다.

그런 다음, 깊이 우선 탐색을 이용해 모든 가능한 순열을 생성하는 재귀 함수 backtrack을 구현합니다.

function backtrack(depth) {
	if (depth === M) {
		console.log(arr.join(" "));
	} else {
		for (let i = 1; i <= N; i++) {
			if (visited[i - 1] === 0) {
				arr[depth] = i;
				visited[i - 1] = 1;
				backtrack(depth + 1);
				visited[i - 1] = 0;
			}
		}
	}
}

 

1. depth가 M에 도달하면, 선택한 숫자들로 만들어진 수열 arr을 출력합니다.
2. depth가 M에 도달하지 않았다면, 1부터 N까지의 숫자들을 반복합니다.

현재 숫자 i가 아직 수열에 사용되지 않았다면(즉, visited[i - 1]이 0이라면), arr[depth]에 i를 할당하고 visited[i - 1]을 1로 설정하여 숫자 i가 사용되었음을 표시합니다.

backtrack 함수를 재귀적으로 호출하여 다음 깊이로 넘어갑니다.

재귀 호출이 끝나면, visited[i - 1]을 다시 0으로 설정하여 숫자 i의 사용 상태를 초기화합니다.

이러한 과정을 통해, 수열 arr에는 중복 없이 1부터 N까지의 숫자 중 M개를 선택한 모든 조합이 생성됩니다.