[자바스크립트] 15650 N과 M (2)

15650번: N과 M (2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

 

입력

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

 

 

출력

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

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

 

 

예제 입력 1

4 2

 

 

예제 출력 1

1 2
1 3
1 4
2 3
2 4
3 4

 

 

자료구조

① 정수: n, m

② 배열: answer

 

 

알고리즘

① DFS 함수:

    a. `dfs(depth, start, arr)`: 깊이 우선 탐색을 수행하는 함수.

    b. `depth`: 현재까지 선택한 숫자의 개수를 나타내는 변수.

    c. `start`: 선택의 시작점을 나타내는 변수.

    d. `arr`: 현재까지 선택한 숫자들을 저장하는 배열.

② 종료조건 및 정답 처리: `depth`가 `m`과 같아지면 현재까지의 순열을 `answer` 배열에 추가하고 함수를 종료한다.

③ 하부단계(함수) 호출:

    a. `for` 루프를 통해 `start` 부터 `n` 까지의 숫자 중에서 아직 선택되지 않은 숫자를 선택한다.
    b. 선택된 숫자를 `arr` 배열에 추가하고, 재귀적으로 다음 단계의 `dfs` 함수를 호출한다.

④ 순열 생성: dfs(0, [])로 초기 호출하여 순열 생성을 시작

 

 

소스 코드 1

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m] = input[0].split(" ").map(Number);

let answer = []; // 순열 결과 저장 배열

function dfs(depth, start, arr) {
  if (depth === m) {
    answer.push([...arr]);
    return;
  }

  for (let i = start; i <= n; i++) {
    dfs(depth + 1, i + 1, [...arr, i]);
  }
}

dfs(0, 1, []);

for (let element of answer) {
  console.log(...element);
}

132ms

① 모든 조합의 수를 고려하기 위해 재귀 함수(백트래킹)을 사용할 수 있다.
② 하나의 조합을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다.

    a. 이때, m개의 원소를 뽑는 순열을 고려하는 것이므로 깊이(depth)는 m과 같다.

③ [조합] 재귀 함수를 호출할 때마다 (자식 노드로 갈수록) 선택되는 값이 커지도록 하는 것이 핵심이다.

    a. 순열 소스 코드와 다른 점은 start 변수가 사용된다. visited 배열은 필요없다. 

 

4개의 수 [1, 2, 3, 4]를 예로 들기

① 깊이(depth)가 2인 경우를 고려한다.

② 경우의 수: (6개)

③ 4개의 수 [1, 2, 3, 4]에서 2개를 고르는 모든 조합을 고려해 보자.

④ [예시] 1 → 3

완전 탐색을 진행하며, 깊이(depth)가 2일 때

 

 

참고

https://www.youtube.com/watch?v=exwk905In0U

나동빈, "JavaScript로 끝내는 자료구조/알고리즘 (코딩 테스트)", [패스트캠퍼스]

 

 

 

✔ 출처

https://www.acmicpc.net/problem/15650