백준 - 10451 순열 그래프

문제

입력

• 첫째 줄

  • 테스트케이스 개수 T

• M개의 줄

  • 순열의 크기 N
  • 순열

제한 조건

• 2 ≤ N ≤ 1,000

예시

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

// NOTE: 출력
3
7

해결

케이스 분리

• 테스트 케이스 T
  - data 객체 분해 할당 할 때, 첫번째 요소로 가져가기
• 각 케이스
  - while 문 시작할 때, 총 2번의 shift를 함
  - 첫번째: 순열의 크기 N
  - 두번째: 순열의 데이터

// NOTE: 입력

2 -------------------------- 테스트 케이스 T
8 -------------------------- 🔥 Case1의 크기 N
3 2 7 8 1 4 5 6 ------------ Case1의 순열 데이터
10 ------------------------- 🔥 Case2의 크기 N
2 1 3 4 5 6 7 9 10 8 ------- Case2의 순열 데이터

makeGraph

• 그래프 생성하는 코드블록
• Array로 생성
  • 단방향 그래프라서 Map은 필요 없다
  • graph[from_node] = to_node
• push로 인접노드 설정
  • 데이터가 1번 정점부터 N번 정점의 인접 노드를 순서대로 가져오기 때문
    - index를 맞추려고 그래프 초기값을 [0]으로 설정

const makeGraph = (n, permutation) => {
    const _graph = [0];
    
    permutation.trim().split(' ').forEach(to => {
        _graph.push(+to); 
    });
    
    return _graph;
};

dfs

• 필요한 파라미터
  - 수열의 크기 N
  • 방문처리 배열 visitedArr
  • 그래프 배열 graphArr
• 이미 방문한 경우
  - return
• 방문하지 않은 경우
  • 방문 처리
    - visitedArr[node] = true로 설정
  • dfs 재귀
    • node를 다음 노드 (graph[node])로 설정
      

const dfs = (node, visitedArr, graphArr) => {
    if (visitedArr[node]) return;
    
    visitedArr[node] = true;
    dfs(graphArr[node], visitedArr, graphArr);
};

전체 코드

const makeGraph = (n, permutation) => {
    const _graph = [0];
    
    permutation.trim().split(' ').forEach(to => {
        _graph.push(+to); 
    });
    
    return _graph;
};

const dfs = (node, visitedArr, graphArr) => {
    if (visitedArr[node]) return;
    
    visitedArr[node] = true;
    dfs(graphArr[node], visitedArr, graphArr);
};

const solution = () => {
    let [T,..._inputs] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split(/\n/);
    T = +T;
    
    while(T--) {
        const N = +_inputs.shift();
        const _graphArr = makeGraph(N, _inputs.shift());
        const _visitedArr = new Array(N + 1).fill(false);
        let _count = 0;
        
        for (let i = 1; i <= N; i++) {
            if (_visitedArr[i]) continue;
            
            dfs(i, _visitedArr, _graphArr);
            _count += 1;
        }
        
        console.log(_count);
    }
};

solution();

---

출처

백준 10451번: 순열 그래프