[백준10451_자바스크립트(javascript)] - 순열 사이클

🔴 문제

순열 사이클

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');

let t = Number(inputs[0]);
let front = 1;

while (t) {
  const n = Number(inputs[front++]);
  const numbers = inputs[front++].split(' ').map((it) => Number(it) - 1);

  let visited = Array.from({ length: n }).fill(false);
  let ans = 0;
  const dfs = (cur, start) => {
    const next = numbers[cur];

    if (visited[next]) {
      ans += 1;
      return;
    }
    visited[next] = true;
    dfs(next);
  };

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs(i);
  }
  console.log(ans);

  t -= 1;
}

🟢 풀이

⏰ 소요한 시간 : -

원래는 텀 프로젝트를 먼저 풀었는데... 아무리봐도 이해가 안돼서 더 쉬운 문제인 순열 사이클 부터 풀어보기로 했다.

테스트 케이스가 복수로 주어지므로 테스트케이스 t를 1씩 줄이면서 n과 numbers를 입력 받는다. 이 때 배열의 인덱스는 0부터 시작되므로 numbers를 입력 받을 때 -1씩 해준다.
그 후 visited 방문 배열과 정답을 체크할 ans 변수를 만들어 준 뒤 dfs함수를 구현한다.
참고로 이 문제는 순열 사이클을 다룬다. 여기서 순열이란 1부터 n까지의 수를 한 번씩 나열한 것 이므로 모든 숫자는 무조건 사이클을 형성한다.
만약 다음위치가 방문한 요소라면 사이클 형성이 완료 된 배열 이므로 dfs를 종료하고 ans를 1증가해준다. 다음위치가 방문하지 않은 배열이라면 방문처리를 한 뒤 dfs를 수행해준다.

배열의 모든요소에 해당 로직을 적용하면 정답

🔵 Ref

https://blahblahlab.tistory.com/116