백준) 10451 - 순열 사이클 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. e.g. 배열 이용, 방향 그래프 사용, 순열 그래프 사용
• 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.
  • 1 -> 3 -> 7 -> 5 -> 1
  • 2 -> 2
  • 4 -> 8 -> 6 -> 4
• N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

시간복잡도

• 각 노드를 한 번씩만 방문하기 때문에 O(n)

알고리즘 선택

• DFS

---

📌 코드 설계하기

1. 문제의 입력값을 개행으로 분리하여 구조분해할당으로 input을 가져옵니다.
2. 입력 배열의 현재 위치를 추적하기 위해 `idx`변수를 초기화합니다.
3. 각 테스트 케이스 처리를 위해 반복분을 만듭니다.
4. 순열 배열을 생성합니다. 0을 첫 번째 요소로 추가하여 1부터 시작하는 인덱싱을 구현합니다.
5. `visited` 배열을 생성하여 각 노드의 방문 여부를 추적합니다.
6. 사이클의 개수를 저장할 `count`변수를 초기화합니다.
7. `DFS`함수를 정의 합니다.

• 현재 노드를 방문했다고 표시합니다.
• 순열에 따라 다음 노드를 결정합니다.
• 다음 노드를 아직 방문하지 않았다면 재귀적으로 DFS를 호출합니다.

  8. 모든 노드에 대해 DFS를 수행합니다.

• 아직 방문하지 않은 노드를 발견하면 새로운 사이클의 시작점으로 간주하고 DFS로 시작합니다.
• 새사이클을 발견할 때마다 `count`를 증가시킵니다.

  9. 발견된 사이클의 총 개수를 출력합니다.

 

---

📌 정답 코드

//https://www.acmicpc.net/problem/10451
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");

let idx = 0;

for (let i = 0; i < n; i++) {
  const num = Number(input[idx++]);
  const arr = [0, ...input[idx++].split(" ").map(Number)];

  const visited = new Array(num + 1).fill(false);
  let count = 0;

  const DFS = (node: number) => {
    visited[node] = true;
    if (!visited[arr[node]]) {
      DFS(arr[node]);
    }
  };

  for (let i = 1; i <= num; i++) {
    if (!visited[i]) {
      DFS(i);
      count++;
    }
  }

  console.log(count);
}