[JavaScript/DFS] 백준 실버 3 : 10451 - 순열 사이클

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

10451번: 순열 사이클

---

📌 작성한 코드

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);
    }

---