https://www.acmicpc.net/problem/10451
10451번: 순열 사이클
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3
www.acmicpc.net
📌 작성한 코드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const T = parseInt(input.shift());
const arr = input.map((i) => i.split(" ").map(Number)).filter((n, i) => i % 2 !== 0);
const makeGraph = (arr) => {
const graph = {};
for (let i = 1; i <= arr.length; i++) {
graph[i] = arr[i - 1];
}
return graph;
};
const permutationCycle = () => {
const dfs = (graph, start, visited) => {
const stack = [];
stack.push(start);
while (stack.length) {
const node = stack.pop();
const next = graph[node];
if (!visited[next]) {
visited[next] = true;
stack.push(next);
}
}
};
for (let i = 0; i < T; i++) {
let count = 0;
const graph = makeGraph(arr[i]);
const visited = new Array(arr[i].length + 1).fill(false);
for (let j = 1; j <= arr[i].length; j++) {
if (!visited[j]) {
dfs(graph, j, visited);
count++;
}
}
console.log(count);
}
};
permutationCycle();
📌 풀이
0. 입력받기
- T의 개수만큼 첫번째에는 순열의 크기, 두번째 줄에는 순열이 주어진다.
- 두개를 혼합해서 받기 까다롭고, 순열의 크기는 .length를 쓰면 된다고 생각했기에 순열만 저장받아서 사용하였다(짝수번째에 순열 저장됨)
const T = parseInt(input.shift());
const arr = input.map((i) => i.split(" ").map(Number)).filter((n, i) => i % 2 !== 0);
1. 간선 그래프 배열 만들기
- 1번 노드가 3번 노드를 가리키고, 2번 노드는 2번 노드를 가리킨다. ...
-> 이런식으로 배열에 순열들이 저장되어 있는데, 몇번 노드가 몇번 노드를 가리키는지 객체에 저장해준다
(배열의 인덱스는 0부터 시작하지만 문제의 인덱스는 1부터 시작하기 때문에 1부터 length까지 확인하면서 저장해준다

const makeGraph = (arr) => {
const graph = {};
for (let i = 1; i <= arr.length; i++) {
graph[i] = arr[i - 1];
}
return graph;
};
2. DFS 사용하기
사이클의 개수를 찾기 위해서는 어떤 사이클이 있는지 경로를 추적해야 한다.
-> DFS 사용해서 사이클 추적
- 노드가 딱 1개의 노드만 가리키고 있기 때문에 반복문을 돌지 않고, 해당 노드가 가리키는 노드만 바로 확인하고 스택에 삽입한다.
const dfs = (graph, start, visited) => {
const stack = [];
stack.push(start);
while (stack.length) {
const node = stack.pop();
const next = graph[node];
if (!visited[next]) {
visited[next] = true;
stack.push(next);
}
}
};
3. 반복문 돌기
- T개의 순열이 주어지기 때문에 T만큼 반복을 돈다.
- 순열을 순서대로 돌면서, 해당 값으로 시작하는 사이클을 찾는다
- 방문처리를 해서 방문되지 않은 값만 사이클의 시작노드로 설정해서 사이클을 찾는다.
- 사이클을 한개를 찾고 나면 count 값을 올려주고, 해당 순열의 사이클 개수를 모두 찾게 되면 console.log()로 출력한다.
for (let i = 0; i < T; i++) {
let count = 0;
const graph = makeGraph(arr[i]);
const visited = new Array(arr[i].length + 1).fill(false);
for (let j = 1; j <= arr[i].length; j++) {
if (!visited[j]) {
dfs(graph, j, visited);
count++;
}
}
console.log(count);
}

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS] 백준 실버 2 : 2644 - 촌수계산 (0) | 2023.09.14 |
|---|---|
| [JavaScript/BFS] 백준 실버 1 : 2667 - 단지번호붙이기 (0) | 2023.09.12 |
| [JavaScript/DFS/BFS] 백준 실버 1 : 1260 - DFS와 BFS (0) | 2023.09.07 |
| [JavaScript/DP] 백준 실버 3 : 14501 - 퇴사 (0) | 2023.08.31 |
| [JavaScript/DFS] 백준 실버 1 : 14888 - 연산자 끼워넣기 (1) | 2023.08.18 |