[JS] N과 M(2)

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

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

function dfs(depth,start,arr){
  if(depth == m){
    console.log(arr.join(" "));
    return;
  }

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

dfs(0,1,[]);

 

✏️ 풀이 방법

---

⁉️ 문제에서 헷갈렸던 부분

 

Q. 어떤 경우에 visited 를 사용하고 어떤 경우에 사용하지 않는걸까?

핵심은 "중복 선택을 막아야 하는 상황인가?" 이다.

 

<visited 배열이 필요한 경우>

 

- 순열처럼 똑같은 원소를 한 번만 써야할 때 

: 각 원소의 사용 여부를 체크하기 위해 필요

 

- 그래프 탐색에서 같은 노드를 재방문하면 안될 때

: 이미 방문한 노드를 다시 방문하지 않도록 visited 로 관리

 

<visited 배열이 필요하지 않은 경우>

 

- 중복 선택이 허용되는 경우 

- 오름차순 / 내림차순 조합

: 조합 문제에서 이미 선택된 숫자 이후부터만 뽑는 경우, start 인덱스만 조정하면 중복이 없으므로 필요가 없다.

 

✍🏻 느낀점

 

뭔가 dfs 의 매개변수가 점점 많아지면서 헷갈리는 것 같다. 오늘 문제에서는 어떨 때는 visited 가 있는 거고, 어떨 때는 없는건지 그게 가장 헷갈리는 부분이었다. 이 문제는 순열(1 2 와 2 1 이 다름) 이 아닌 조합(1 2 와 2 1 이 같음) 문제이기 때문에, start 인덱스를 통해 중복이 자연스럽게 방지돼 visited 가 필요가 없다고 한다. 이런 부분들에 좀 익숙해져야될 것 같다. 퍼플렉시티는 아래와 같이 대답을 해줬다.