10451번 '순열 사이클'

import java.io.*;

import java.util.*;

class Edge {

int start;

int end;

Edge(int start, int end) {

this.start = start;

this.end = end;

}

}

class Main {

static boolean[] isChecked;

static Edge[] array;

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

int cases = Integer.parseInt(in.readLine());

for(int i=0; i<cases; ++i) {

int result = 0;

int number = Integer.parseInt(in.readLine());

String[] input = in.readLine().split(" ");

array = new Edge[number + 1];

for(int j=1; j<=number; ++j) {

array[j] = new Edge(j, Integer.parseInt(input[j - 1]));

}

Arrays.sort(array, new Comparator<Edge>() {

@Override

public int compare(Edge o1, Edge o2) {

return 1;

}

});

isChecked = new boolean[number + 1];

for(int j=1; j<=number; ++j) {

if(isChecked[j] == true) {

continue;

}

Edge edge = array[j];

isChecked[j] = true;

int index = edge.end;

while(isChecked[index] == false) {

edge = array[index];

isChecked[index] = true;

index = edge.end;

}

++result;

}

System.out.println(result);

}

}

}

방향 그래프이고, 정점에서 뻗어가는 간선이 하나밖에 없으므로

연결리스트로 그래프를 표현하지 않아도 되었다.

시작 정점에서부터 탐색을 시작하고, 탐색 여부를 확인하는 배열을 만들어 준 후

어떠한 정점이 탐색된 상태로 나올 때까지 서로 연결된 정점을 탐색해간다.

글로 쓰려니 쉽게 안써진다...

아무튼 탐색 도중 탐색된 정점이 나오면 사이클을 이루었다는 말이므로 프린트할 값을 1 증가시킨다.

Swift로는 간단하게 튜플을 요소로 갖는 배열을 만들어 풀었다.

let cases = Int(readLine()!)!

for _ in 0..<cases {

    var result = 0

    let number = Int(readLine()!)!

    var array = [(Int, Int)].init(repeating: (0, 0), count: number + 1)

    var isChecked = [Bool].init(repeating: false, count: number + 1)

    let input = readLine()!.split(separator: " ").map { Int($0)! }

    for i in 1...number {

        array[i] = (i, input[i - 1])

    }

    array.sort { $0.0 < $1.0 }

    for i in 1...number {

        if isChecked[i] {

            continue

        }

        var edge = array[i]

        isChecked[i] = true

        var index = edge.1

        while !isChecked[index] {

            edge = array[index]

            isChecked[index] = true

            index = edge.1

        }

        result += 1

    }

    print(result)

}