백준 - 9466 텀 프로젝트

Park Inhye·2024년 3월 26일

코테

코테 연습

목록 보기

27/37

문제

입력

첫째 줄
- 테스트케이스 개수 T
M개의 줄
- 순열의 크기 N
- 순열

제한 조건

2 ≤ n ≤ 100,000

예시

// NOTE: 입력
2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

// NOTE: 출력
3
0

해결

문제의 핵심

다시 방문한 곳에서 순열 구하기

makeGraph

숫자의 자릿수를 작은 순서대로 재배치하는 코드블록

const makeGraph = (n, permutation) => {
    return [0, ...permutation.trim().split(' ').map(v => +v)];
};

dfs

필요한 파라미터
- 현재 정점 node
무조건 현재 노드를 방문처리하고
다음 노드를 방문하지 않았으면,
- dfs 탐색을 진행
다음 노드를 이미 방문한 경우
- 순열 개수를 구한다
- 개수를 구했으면, 현재 정점의 doneArr을 true로 처리하여 순열을 구했음을 표기한다.

const dfs = (node) => {
    _visitedArr[node] = true;
    const _next = _graphArr[node];
    
    if (!_visitedArr[_next]) dfs(_next);
    else if (!_doneArr[_next]) {
        for (let i = _next; i !== node; i = _graphArr[i]) {
            _count += 1;
        }
        
        _count += 1;
    }
    
    _doneArr[node] = true;
};

전체 코드

// NOTE: 전역변수
let _graphArr;
let _visitedArr;
let _doneArr;
let _count = 0;

// NOTE: 솔루션
const makeGraph = (n, permutation) => {
    return [0, ...permutation.trim().split(' ').map(v => +v)];
};

const dfs = (node) => {
    _visitedArr[node] = true;
    const _next = _graphArr[node];
    
    if (!_visitedArr[_next]) dfs(_next);
    else if (!_doneArr[_next]) {
        for (let i = _next; i !== node; i = _graphArr[i]) {
            _count += 1;
        }
        
        _count += 1;
    }
    
    _doneArr[node] = true;
};

const solution = () => {
    let [T,..._inputs] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split(/\n/);
    T = +T;

    while(T--) {
        const N = +_inputs.shift();
        _graphArr = makeGraph(N, _inputs.shift());
        _visitedArr = Array(N + 1).fill(false);
        _doneArr = Array(N + 1).fill(false);
        
        for (let i = 1; i <= N; i++) {
            if (_visitedArr[i]) continue;
            
            dfs(i);
        }
        
        console.log(N - _count);
        _count = 0;
    }
};

solution();